找到给定素数后的n个素数,而不使用任何检查素数的函数

Question

如何编写一个程序来查找给定数字后的n个素数？例如,在100之后的前10个素数,或在1000之后的前25个素数.编辑:下面是我尝试的.我正在以这种方式获得输出,但是我们可以在不使用任何素性测试函数的情况下进行输出吗？

#include<stdio.h>
#include<conio.h>
int isprime(int);
main()
{
    int count=0,i;
    for(i=100;1<2;i++)
    {
        if(isprime(i))
        {
            printf("%d\n",i);
            count++;
            if(count==5)
                break;
        }
    }
    getch();
}
int isprime(int i)
{
    int c=0,n;
    for(n=1;n<=i/2;n++)
    {
        if(i%n==0)
        c++;
    }
    if(c==1)
        return 1;
    else
        return 0;
}

Answer 1

当然.阅读有关Eratosthenes筛选的信息.您可以生成素数,而不是检查素数.

Answer 2

实施Eratosthenes的胶印筛.它只是两个循环,一个接一个,在另一个循环内.

#include <math.h>             // http://ideone.com/38MQlI
#include <stdlib.h>
#include <stdio.h>

typedef unsigned char bool;   // quick'n'dirty

void primes (int n, int above)
{
  double n0 = above / ( log(above) - log(log(above)) ); // ~ 11%..16% overhead
  int i=0, j=0, k=0;
  double top = n*log(above)*log(log(above)) + above;    // approximated
  int lim = sqrt(top), s2 = top - above + 1;

  bool *core = (bool*) calloc( lim+1, sizeof(bool));    // all
  bool *offset = (bool*) calloc( s2+1,  sizeof(bool));  //   zeroes

  for( i=4; i<=lim; i+=2 ) core[i]=1;      // `1` marks composites
  for( i=above%2; i<=s2; i+=2 ) offset[i]=1;            // (even numbers)

  for( i=3; i<=lim; i+=2 )
    if( !core[i] )                         // `0` marks primes
    {
      k = 2*i;

      for( j=i*i; j<=lim; j+=k )
          core[j] = 1;

      for( j=(k-(above-i)%k)%k; j<=s2; j+=k )    // hopscotch to the top
          offset[j] = 1;
    }

  printf(" %d +: ",above);
  for( i=0; i<=s2 && n>0 ; ++i )
    if( !offset[i] )                       // not a composite,
    {
      printf(" %d", i);                    // thus, a prime
      --n;
    }
}

int main()
{
  // primes(10,1000);        // 1000 +:  9 13 19 21 31 33 39 49 51 61
  // primes(10,100000);     // 100000 +:  3 19 43 49 57 69 103 109 129 151
  primes(10,100000000);    // 100000000 +:  7 37 39 49 73 81 123 127 193 213
                          // 1000000000 +:  7 9 21 33 87 93 97 103 123 181
  return 0;
}

您可以在此处添加许多改进.