Myujth

I'm trying to find the first prime number after n, unless entered n is already prime (then the program prints out n and terminates).

Example input:

n = 7

The first prime number is: 7 (Good)

n = 591

The first prime number is: 591 (Not right, 591 is not a prime number)

n = 14

The first prime number is: 15 (This is also false, shouldn't it be 17?)

Where am I making a mistake? It might be an obvious one, but I'm just starting out.

#include <stdio.h>

int main()

int i = 2, n, m;

printf("n = ");

do
scanf("%d", &n);
while (n < 2);

m = n / 2;

if (n == 2)
 printf("The first prime number is: %d", n);
 return 0;


while ( i <= m )

 if (n % i == 0)
 n++;

 if (n % i != 0)
 printf("The first prime number is: %d", n);
 return 0;
 else i++;



return 0;

Your logic for determining a prime number is wrong.

First of all you should write a function ( not necessarily but it is recommended ) to check whether one number is prime. Here's the code for this function:

 int checkPrimeNumber(int n)
 
 int j, flag = 1;

 for(j=2; j <= n/2; ++j)
 
 if (n%j == 0)
 
 flag =0;
 break;
 
 
 return flag;
 

Once you include the function your while loop should loop until if finds the first prime number starting from N using that function. Below is a code for that function.

You can also check this answer here:
https://codereview.stackexchange.com/questions/71212/find-smallest-prime-number-greater-than-given-n

The following two pieces of logic should solve your problem.

int IsPrime(int n)

 int i;
 for( i=2; i <= n/i; i++)
 if( n%i == 0 ) return 0;
 return 1;

This function determines reasonably quickly whether the integer passed in is prime. It stops testing once it has passed the square root of the test integer.

int FirstPrime(int n)

 while( !IsPrime(n) )
 n++;
 return n;

This function contains the basic logic set out in your problem statement: return the input value, if prime, or failing that the first integer after that value that is prime.

Breaking the code into separate functions makes it much easier to test and to reason about the code.

Checking primality

This is the simpler code that I use for detecting primes:

int isprime(unsigned number)

It exploits the fact that all prime numbers larger than 3 have the form 6N±1. It's easy to see why. All the numbers of the forms 6N+0, 6N+2, 6N+4 are clearly divisible by 2 and the numbers of the form 6N+3 are clearly divisible by 3, which leaves only 6N+1 and 6N+5 as possibly prime — and 6N+5 is equivalent to 6(N+1)-1, so the formula 6N±1 covers them properly. For N = 1, 6N±1 yields 5 and 7 which are prime; N = 2 yields 11 and 13 which are prime; N = 3 yields 17 and 19 which are prime; N = 4 yields 23 and 25, of which 23 is prime and 25 is not. All primes bigger than 3 are of the form 6N±1; not all numbers of the form 6N±1 are prime. All this means that the code only checks two divisors out of every six as it steps through the range up to the square root of the number.

I have a more complex variant which knows the primes up to 100, and then goes stepping every 6:

int isprime(unsigned number)

This is usually marginally faster than the other, but only by a very small amount.

Next prime after

I originally wrote this code for another SO question that was deleted before I posted an answer; it uses another variant of isprime() with a table of primes up to 1013.

/* Inspired by the deleted question SO 5308-6674 */
/* Determine the next prime after a given number */

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

#define NEXT_PRIME_AFTER /* Avoid unnecessary checks in is_prime() */

#ifdef TEST
static unsigned primes = 2, 3, 5, 7, 11 ;
#else
static unsigned 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,
;
#endif /* TEST */

enum N_PRIMES = sizeof(primes) / sizeof(primes[0]) ;

/*
** In the context of next_prime_after(), this function is never called
** upon to validate small numbers - numbers less than primes[N_PRIMES-1]
** are not passed here. In more general contexts, the extra conditions
** in the conditionally compiled code are necessary for accuracy.
*/
static bool is_prime(unsigned p)

 for (int i = 0; i < N_PRIMES; i++)
 
#ifndef NEXT_PRIME_AFTER
 if (p < primes[i])
 return false;
 if (p == primes[i])
 return true;
#endif /* NEXT_PRIME_AFTER */
 if (p % primes[i] == 0)
 return false;
 
 for (unsigned t = primes[N_PRIMES - 1]; t * t <= p; t += 6)
 
 if (p % t == 0)
 return false;
 if (p % (t + 2) == 0)
 return false;
 
 return true;


static unsigned next_prime_after(unsigned start)

 for (int i = 0; i < N_PRIMES; i++)
 
 if (start < primes[i])
 return primes[i];
 
 for (unsigned x = (start + 1) / 6; x < UINT_MAX / 6; x++)
 
 unsigned t = 6 * x - 1;
 if (t > start && is_prime(t))
 return(t);
 t += 2;
 if (t > start && is_prime(t))
 return(t);
 
 return 0;


int main(void)

 assert((primes[N_PRIMES-1]+1) % 6 == 0);
 for (unsigned u = 0; u < 100; u++)
 printf("%3u => %3un", u, next_prime_after(u));
 for (unsigned t = 100, u = next_prime_after(t); u < 12345678; t = u)
 printf("%3u => %3un", t, (u = next_prime_after(t)));

Be wary of the isprime() function here. It is tailored to this context and omits checks that would be necessary with a general purpose, standalone prime tester. The next_prime_after() steps through the list of known primes (if you're likely to be dealing with many big possible primes, you might add a test to see whether it is worth stepping through the first loop at all), and then steps through the 6N±1 sequence looking for a prime.

The test code prints the next prime after each number from 0 to 99. Thereafter, it steps through the primes up to 12345701 (which is the first prime after 12345678).

 0 => 2
 1 => 2
 2 => 3
 3 => 5
 4 => 5
 5 => 7
 6 => 7
 7 => 11
 8 => 11
 9 => 11
 10 => 11
 11 => 13
 12 => 13
 13 => 17
 14 => 17
 15 => 17
 16 => 17
 17 => 19
 18 => 19
 19 => 23
 20 => 23
 21 => 23
 22 => 23
 23 => 29
…
 95 => 97
 96 => 97
 97 => 101
 98 => 101
 99 => 101
100 => 101
101 => 103
103 => 107
107 => 109
109 => 113
113 => 127
127 => 131
…
12345581 => 12345623
12345623 => 12345637
12345637 => 12345643
12345643 => 12345647
12345647 => 12345653
12345653 => 12345701