NBP部落格-分享是為了成長

010.產生由 1 到 n (n = 1) 之間的所有質數


原發表者：black j

//開根另解:Newton's method Start with x = k. Compute (x^2 + k)/(2x) and use this for the next value of x.

#include <iostream.h>
#include<cstdlib>
#include<cmath>

void main()
{
double n;
double x=0;

cin>>n;
x=n;

for (int i=0;i<100;i++)
{
　x=(x*x+n)/(2*x);
}

cout<<"the square root is "<<x<<endl;
cout<<sqrt(n);//比較結果
}

原發表者：kyoyen

#include <stdio.h>

int main(void)
{
unsigned long long n, i, j;

printf("Please input a number to find from 1 to n prime(>=1, q to quit):");

while((scanf("%llu", &n)) == 1)
{

 for(i = 1; i <= n; i++)
 {
  for(j = 2; j < i; j++)
   if((i % j) == 0)
    break;

   if(i == j)
    printf("%llu ", i);
 }

 printf("\nPlease input a number to find from 1 to n prime(>=1, q to quit):");
}
return 0;
}

原發表者：happylin
sorry 內有兩個用一樣發法找prime 的程式. 請自行辨認
想法很簡單, 就是用刪除法, 不過缺點. 會消耗很多memory

/*
Filter prime
compiler : VC++ 6.0

find all prime small than a number

note :
MaxNumber define in d_nMaxNumber
if your system don't have much memory, modify it to small.
*/

#include <stdio.h>
#include <assert.h>

const int d_nMaxNumber=1000*1000*1000;


void Init(char* o_pPrimeBuffer,int a_nElement)
{
assert(o_pPrimeBuffer!=NULL);
assert(a_nElement <= d_nMaxNumber );
assert(a_nElement >=1);
int i;
for( i =1; i <= a_nElement; ++i )
 o_pPrimeBuffer[i]=i&1; // 所有2 的倍數都設為0 不是2 的都設為1
if( a_nElement >= 2 ) o_pPrimeBuffer[2]=1;
o_pPrimeBuffer[1]=1;
}

void FilterParime(char* o_pPrimeBuffer,int a_nElement)
{
assert(o_pPrimeBuffer!=NULL);
assert(a_nElement <= d_nMaxNumber );
assert(a_nElement >=1);

int i;
int j;
for( i = 3; i*i <= a_nElement; i+=2)
{
 if( o_pPrimeBuffer[i] != 1 ) continue;
 for( j = i+i+i; j <= a_nElement; j+=(i+i) )  // 去除所有i 奇數部分的倍數
  o_pPrimeBuffer[j]=0;
}

// loop 跑完後.. o_pPrimeBuffer[i] == 1 時 i 為prime
}

void PrintResult(const char* a_pPrime,int a_nElement)
{
assert(a_pPrime!=NULL);
assert(a_nElement <= d_nMaxNumber );
assert(a_nElement >=1);
printf("All Prime Number small then %d is :\n",a_nElement);
for( int i = 2; i <= a_nElement; ++i)
{
 if( a_pPrime[i] == 1 )
 {
  printf("%d\n",i);
 }
}
}

/// Filter Prime 2
int Init2(char** o_pPrimeBuffer,unsigned int a_nN)
{
if( a_nN <= 2 ) return 0;
size_t nElement=(a_nN-1)/2;
*o_pPrimeBuffer=new char[nElement];
for( int i = 0; i < nElement; ++i )
 (*o_pPrimeBuffer)[i]=1;
return nElement;
}

unsigned ToNumber(unsigned i)
{
return i*2+3;
}

void FilterPrime2(char* o_pPrimeBuffer,int a_nElement)
{
assert(o_pPrimeBuffer != NULL);
if( a_nElement == 0 ) return;


int nPrime;
int nRemoveIndex;
int nStep;
for( nPrime = 0; nPrime*nPrime < ((a_nElement)/2); ++nPrime)
{
 if( o_pPrimeBuffer[nPrime] == 0 ) continue;
 nStep=ToNumber(nPrime);
 for( nRemoveIndex = nStep+nPrime; nRemoveIndex < a_nElement; nRemoveIndex+=nStep)  // 去除所有倍數
  o_pPrimeBuffer[nRemoveIndex]=0;
}
}

void Result2(const char* o_pPrimeBuffer,int a_nElement)
{
printf("2\n");
if( a_nElement != 0 )
{
 for( int i =  0; i < a_nElement; ++i )
  if( o_pPrimeBuffer[i] == 1 )
  {
   printf("%d\n",ToNumber(i));
  }
}
}


int main()
{
unsigned nElement;
char *pPrime;
unsigned nPrime;
printf("Please input a number must small then %d : ",d_nMaxNumber);
scanf("%d",&nElement);

if( nElement > d_nMaxNumber )
{
 printf("Error, your input %d is to large",nElement);
 return 1;
}
if( nElement <= 1 )
{
 printf("Error, your input %d is to small",nElement);
 return 1;
}

nPrime=Init2(&pPrime,nElement);
FilterPrime2(pPrime,nPrime);
Result2(pPrime,nPrime);
}

int mainxx(int argc,char *argv[])
{
int nElement;
char *pBuffer;
char *pPrime;
printf("Please input a number must small then %d : ",d_nMaxNumber);
scanf("%d",&nElement);

if( nElement > d_nMaxNumber )
{
 printf("Error, your input %d is to large",nElement);
 return 1;
}
if( nElement <= 1 )
{
 printf("Error, your input %d is to small",nElement);
 return 1;
}

pBuffer=new char[nElement];
pPrime=pBuffer-1;
Init(pPrime,nElement);
FilterParime(pPrime,nElement);
PrintResult(pPrime,nElement);

delete pBuffer;
return 0;
}

原發表者：rclrn

//10.產生由 1 到 n (n >= 1) 之間的所有質數。
//compiled by Borland C++ Builder 6
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

bool testPrime(const int prime[], const int& test);

int main()
{
 int n = 0;
 cout << "Enter n : ";
 cin >> n;

 int* prime = new int[n/3 + 2];
 prime[0] = 2;
 prime[1] = 3;

 int count = 2;
 int test = 5;

 for(int i = 1; test <= n; i++)
 {
   if(testPrime(prime, test))
     prime[count++] = test;
     
   if(i % 2)
     test += 2;         //6k + 1
   else
     test += 4;         //6k + 5
 }

 for(int i = 0; i < count; i++)
 {
   if(i % 5 == 0)
     cout << endl;
   cout << setw(7) << prime[i];
 }

 delete [] prime;
 cout << endl;
 system("pause");
 return 0;
}

bool testPrime(const int prime[], const int& test)
{
 for(int j = 0; prime[j] <= sqrt(static_cast<double>(test)); j++)
   if(test % prime[j] == 0)
     return false;
 return true;
}

原發表者：watershed

#include<stdio.h>
main()
{
 int n,prime_number[100000]={0};
 while( scanf("%d",&n)==1 && n ) {
   int i,j;
   prime_number[2]=1;
   for(i=3; i<n; i+=2) prime_number[i]=1;
   for(i=3; i<n; i+=2)
     for(j=3; j*i<n; j+=2) prime_number[i*j]=0;
   printf("2");
   for(i=3; i<n; i+=2)
     if( prime_number[i] ) printf(" %d",i);
   printf("\n");
 }
}

原發表者：andyeric

/*010.產生由 1 到 n (n = 1) 之間的所有質數。*/
#include <iostream.h>
#include <conio.h>
#include <math.h>

int main()
{
int n,count;
cin>>n;
for(int i=2;i<n;i++)
{
 count=0;
 //原程式 for(int j=2;j<sqrt(i);j++)
 for(int j=2;j<=sqrt(i);j++) // Pirate修正
 {
  if(i%j==0) count++;
 }
 if(count==0)
 cout<<i<<" ";
}
getch();
return 0;
}

原發表者：ru0217

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int num,m,n,cnt=0;
printf("input a number:");
scanf("%d",&num);
for(m=2;m<=num;m++)
 for(n=2;n<=m;n++)
 {
  if(m%n==0 && n!=m)
  break;
  else if(n==m)/* prime found */
  {
   cnt++;
   printf("%5d:%-5d\n",cnt,n);
  }
 }
system("PAUSE");
return 0;
}

原發表者：zoe

/* 產生由 1 到 n (n >= 1) 之間的所有質數。 */

#include <stdio.h>
#include <math.h>

#define max 2000

main()
{
       int n, i, j, k, b;
       int prime[max] = {2, 3};                /* 質數陣列 */
       double s;                               /* i 平方根 */

       scanf("%d", &n);

       k = 2;                                  /* prime 註標 */

       for ( i = 3; i <= n; i++ )
       {
               b = 0;
               s = sqrt((double)i);

               /* 用小於根號 i 的質數除, 因為電腦計算完全平方數可能出錯, 所以 s + 1 */
               for ( j = 0; j < k && prime[j] < s + 1; j++ )
               {
                       if ( i % prime[j] == 0 )
                       {
                               b = 0;
                               break;
                       }
                       else
                               b = 1;
               }

               if ( b == 1 )
               {
                       prime[k] = i;
                       k++;
               }
       }

       for ( i = 0; i < k; i++ )
               printf("%d\n", prime[i]);
}

原發表者：blueluna

#include "iostream.h"
int main()
{
 int i,j,k=1,exc,n,num[10000];
 num[0]=1,num[1]=2;
 cout<<"****產生由 1 到 n (n = 1) 之間的所有質數****\n\n";
 cout<<"請任意輸入一個正整數n:";
 cin>>n;
 if (n>1)
 {
  if (n==2)
  {
   cout<<"所有的質數為:\n1,2\n";
  }  
 
  else
  {  cout<<"所有的質數為\n";
  cout<<"1,2,";
 for (i=2;i<=n;i++)
 {
           exc=0;
  for (j=1;j<=k;j++)
  {
    if (i%num[j]==0)
                 exc=1;
  }
  if (exc==0)
  {
             k++;
    num[k]=i;
    cout<<num[k]<<",";
  }
 }
  }
 }
 else if (n==1)
 cout<<"所有的質數為:1\n";
return 0;
}

在此感謝當年在數位高手(NBP)分享的朋友，本人將資料彙整於此並盡量將當初發表者名稱註記。