素数をチェックする関数を使用せずに、指定された素数の後にn個の素数を見つける

Question

与えられた数の後に素数を見つけるプログラムを書く方法？例： 100の後の最初の10つの素数、または1000の後の最初の25の素数。 編集： 以下は私が試したものです。私はそのように出力していますが、primality-testing関数を使用せずに行うことはできますか？

#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

です。 Sieve of Eratosthenesについて読む素数をチェックする代わりに、素数を生成します。

Answer 2

例えば、100の後に10の素数を見つけたいと思っています。効率的なものではない5つの数字が偶数であり、他の5つの数字については、 、7,9）が0であるかどうかは、それらのすべてではない場合は、素数です。

Answer 3

#include <stdio.h> 

static int primes[] = { 
    2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 
    101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199, 
    211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293, 
    307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397, 
    401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499, 
    503,509,521,523,541,547,557,563,569,571,577,587,593,599, 
    601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691, 
    701,709,719,727,733,739,743,751,757,761,769,773,787,797, 
    809,811,821,823,827,829,839,853,857,859,863,877,881,883,887, 
    907,911,919,929,937,941,947,953,967,971,977,983,991,997, 
    1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097, 
    1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193, 
    1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297, 
    1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399, 
    1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499 
}; 
int primeN = sizeof(primes)/sizeof(int); 

void printPrime(int n, int count){ 
    int i; 
    for(i=0;primes[i]<n;i++); 
    while(count){ 
     printf("%d\n", primes[i++]); 
     count--; 
    } 
} 

int main(){ 
    printf("first 10 primes after 100\n"); 
    printPrime(100, 10); 
    printf("first 25 primes after 1000\n"); 
    printPrime(1000, 25); 
    getch(); 
} 

Answer 4

エラトステネスのオフセット篩を実装します。別のループの中に次々に2つのループがあります。

#include <math.h>    // http://ideone.com/va7jm 
#include <stdlib.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 n1 = n0+n, i=0, j=0, k=0; 
    double top = n1*(log(n1) + log(log(n1))); // overestimation 
    int lim = sqrt(top), s2=top-above+1; 

    bool *composit = (bool*) calloc(lim+1, sizeof(bool)); 
    bool *range = (bool*) calloc(s2+1, sizeof(bool)); 

    for(i=4; i<=lim; i+=2) composit[i]=1; // "1" marks composites 
    for(i=above%2; i<=s2; i+=2) range[i]=1; 

    for(i=3; i<=lim; i+=2) 
    if(!composit[i])      // "0" marks primes 
    { 
     k = 2*i; 
     for(j=i*i; j<=lim; j+=k) 
     if(!composit[j])  // 2.99s vs 3.26 for primes(10,10^9) 
      composit[j] = 1; 
     for(j=(k-(above-i)%k)%k; j<=s2; j+=k) 
     if(!range[j]) 
      range[j] = 1; 
    } 

    printf(" %d +: ",above); 
    for(i=0; i<=s2 && n>0 ; ++i) 
    if(!range[i])      // not a composite 
    { 
     printf(" %d", i); 
     --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; 
} 

ここに追加できる改善点はたくさんあります。