Program to find a prime number after a given number: I used the theory that prime numbers are divisible by only 2 numbers 1 and itself.

#include <stdio.h>
#include <conio.h>
int main(int argc, char const *argv[])
{
   int num,a=0,i,j;
   printf("Enter a number: ");
   scanf("%d",&num);
   for(i=num 1;i>0;i  ){
       for(j=1;j<=i;j  ){
           if(i%j==0){
              a=a 1;
           }
       }
       if(a==2){
           printf("%d",i);
           break;
       }
   }
   return 0;
}

This code is working only for a single increment like if user gives the input as 4 it is returning the output as 5. But it wont return output if input is given as 7 (it should return 11)

Then I modified the code as below :

#include <stdio.h>
#include <conio.h>
void main(int argc, char const *argv[])
{
   int num,a=0,i,j;
   printf("Enter a number: ");
   scanf("%d",&num);
   for(i=num 1;i>0;i  ){
        a=0;
        for(j=1;j<=i;j  ){
            if(i%j==0){
               a=a 1;
            }
        }
        if(a==2){
            printf("%d",i);
            break;
        }
    }
}

This one runs well. I am confused why the program gives the output if i declared the variable after the for loop but fails to give it if declared before?

CodePudding user response：

Notice the a variable is not changed through the bigger for loop.

Meaning, after the first iteration we'll have a>=2 (since every number has at least 2 divisors, while primes have precisely 2), and at the next iteration, this value does not reset.

You can try and print the value of a in every iteration from the first code snippet to make sure :)

CodePudding user response：

your problem is so simple, it's because the a isn't reset (become 0 again) after the end of the big for loop, so it maintains its old value.

you don't have to loop all over the number till that number to find if it's divisible only by itself and 1 or not.

you could the theorem that says :

To test whether a number is prime or not, we can test whether it is divisible only up to the square root of that number

refer to this question on stack overflow and this small tutorial

here in your code, you are using an O(n) time, but using this theorem, you can reduce time to O(log(n)), so the code can be modified:

instead of :

for(j=1;j<=i;j  ){

you can write:

for(j=2;j<= sqrt(i);j  ){

and change :

if(a==2){

into

if(a == 0){

and so the full code become:

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

int main(int argc, char const *argv[])
{
    int num,a=0,i,j;
    printf("Enter a number: ");
    scanf("%d",&num);
    for(i=num 1;i>0;i  ){
        a=0;
        for(j=2;j <= sqrt(i);j  ){
            if(i%j==0){
                a=a 1;
            }
        }
        if(a == 0){
            printf("%d",i);
            break;
        }
    }

    return 0;
}

and this is some example output:

Enter a number:7
 11

Enter a number:5
 7

Enter a number:42
 43