Find n primes after a given prime number, without using any function that checks for primality

Question

How to write a Program to find n primes after a given number? e.g. first 10 primes after 100, or first 25 primes after 1000. Edited: below is what I tried. I am getting output that way, but can we do it without using any primality-testing function?

#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;
}

Fewell

Did you try to compile this? My guess is no. Some remarks: don't use a break but add the end condition in a for loop, the 3th line (isprime(i) is a function call but the function itself is not implemented and there should be an if before, count is not initialized and not needed because i is the counter and printf should state the type to print. Since this is homework you should add that tag. – Sasin

The printf() needs a format specification for the integer, and probably a newline at the end too. – Gallia

Answer 1

Sure. Read about the Sieve of Eratosthenes. Instead of checking for primality, you generate prime numbers.

Sodomy

you probably meant "you generate [and discard] multiples of prime numbers". – Tour

@WillNess No, not really. Yes, of course I agree that the sieve works by eliminating all the composite numbers. What I was trying to say, though, is that if you want to avoid the need for a function that checks primality (as the Q title indicates), you can turn the problem on its head and generate primes instead. – Sodomy

Answer 2

Implement the "offset" sieve of Eratosthenes. It is just two loops, one after another, inside another loop.

#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;
}

There are many improvements yet that you can add here. For instance, instead of marking the evens, just don't represent them altogether.

Tour

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();
}

Drisko

Answer 4

For example you want to find 10 primes after 100. One way (not an efficient one) is that we know that 5 numbers are even and are not prime so for other five numbers check whether their mod to (3,5,7,9) are 0 or not if not for all of them, then it is prime number.

Grisette

I don't understand this answer. Which five numbers are even? – Indiction

100,101,102,103,...,110 you have to check only 5 numbers to see whether they are prime or not. – Grisette

That doesn't find 10 primes after 100. It checks the first 10 numbers to see if they're prime. That's not the same problem at all. – Indiction

I suspect that 'even numbers and multiples of 5 are not prime' is what was intended. – Gallia

Actually, since the first 10 primes larger than 100 are all less than 169 (or 13 * 13), you can simply check for divisibility of the odd numbers by the odd numbers 3, 5, 7, (9), 11, 13 and be done. You might get away without checking 13, but it is borderline. – Gallia

i welcome if someone comes with out using any function in the code – Fewell

@caleb i know that Sieve of Eratosthenes, problem is with out using any functione can i get the desired output – Fewell

@GorijavoluKarthik sieve of E. is not a function, it is algorithm. – Tour