Thread: C program for prime numbers

Post your program.

This is an example of problem which is straightforwards, but not absolutely trivial, to solve for small numbers, and a mathematical research problem to solve quickly for large numbers.
The first thing to do is to write a completely naive function, with no attempt at optimisation whatsoever, that tells you whether a number has any factors of 2 or greater.
Then think 1), what is the greatest factor possible, and how can I calculate it efficiently (there's a function which will do this for you, which is a bit of a cheat), 2) do I need to try every number as a factor, or are there some I can eliminate, how much speed up will I get by eliminating some tests?).
Then run lots and lots of tests on random numbers, calling your naive function and the efficient one. Do they always give the same results?

Is your variables the alphabet or am I mistaken? Probably the second, but should name your variables with names that represent what they mean and their usage.
For example, if I want to calculate the sum of 0, 1 ,2 and 3, I would name the variable that accumulates the result as sum and not as bla.
First think the mathematical method. When does a number is prime?

Originally Posted by arslan20

Here is my rough program

Code:

#include<stdio.h>
#include<conio.h>
int main(void)
{
    int a,b,c,d,e,f,g,h,i;
    printf("Enter a number");
    scanf("%d",&a);
    b=a%2;
    if (b==0)
    printf("number is not prime");
    else
    c=a%3;
    if (c==0)
    printf("number is not prime");
    else
    d=a%4;
    if (d==0)
    printf("number is not prime");
    else
    e=a%5;
    if (e==0)
    printf("number is not prime");
    else
    f=a%6;
    if (f==0)
    printf("number is not prime");
    else
    g=a%7;
    if (g==0)
    printf("number is not prime");
    else
    h=a%8;
    if (h==0)
    printf("number is not prime");
    else
    i=a%9;
    if (i==0)
    printf("number is not prime");
    else
    printf("number is prime");
    getch();
}

Ok, I see the problem.

Programming variables are not the same as algebra unknowns.
In algebra if we say b = a % 2 and c = a % 3, then b and c must retain those values for the rest of the calculation. So you need
a new symbol for each value.
In programming we often say things like x = x +1. Which means
take x, add one to it, and set x to the new value. It's virtually
essential to do this, because programming is all about loops, doing the same calculation over and over again with slightly different values.
You only need one or two variables to write your program.

This code is unacceptable to anyone who knows how to program. You must use a loop here.

Here is a modified version of the program, still not using loops, and yes it's using goto's but at least it shows the basic logic to determine if a number is prime. It would be better to create a program to generate an array of prime numbers up to some value "n", using a loop.

Code:

#include<stdio.h>
#include<conio.h>

int main()
{
    int a;
    printf("Enter a number: ");
    scanf("%d",&a);
    if ((a%2)==0 && a != 2)
        goto notprime;
    if ((a%3)==0 && a != 3)
        goto notprime;
    if ((a%5)==0 && a != 5)
        goto notprime;
    if ((a%7)==0 && a != 7)
        goto notprime;
    if ((a%11)==0 && a != 11)
        goto notprime;

    printf("number is prime");
    goto exit0;

notprime:
    printf("number is not prime");

exit0:
    getch();
}

Gack! I thought my cat had a furball in his throat. I realise now that it is code from this thread.

The OP may want to look up "Sieve of Eratosthenes". It is an approach for searching for primes.

If that is too hard, you might want to also think about how to simplify your approach. For example, I bet that there is no number divisible by 6 that is not divisible also by 2 and by 3. So if a value is not divisible by 2 it cannot be divisible by 6.

Welcome to the forum, arslan20!

Don't worry that your code is "not acceptable" - because no real beginner's code is acceptable. We just aren't born with the knowledge and skill of C programming already inside. By definition, every beginner's code is unacceptable, until they've mastered the basics, at least.

For now, stick with the "Trial by Division" method of finding out whether a number is prime or not. That is exactly what you posted that you want to do.

Take a simple example, and work it through, (may take several times, before the "light" of understanding turns on), but study the patterns you see as you do it.

Say I ask you if the number 9 is prime. You could see it being solved by a series of steps, like this:

Code:

// if the remainder of 9/2 is 0
if(9 % 2 == 0) 
   9 is not prime

// if the remainder of 9/3 is 0
if(9 % 3 == 0)
    9 is not prime

Now the challenge is to put the two tests shown above, into a loop, because programming uses loops VERY heavily indeed. You could use either a for loop, or a while loop. A while loop, in pseudo code might look like:

Code:

int i = 2;
int n = 9;
while(n % i not equal zero, and i is less than n )
   increment i

Study that logic, and start working out how it can be done, using a loop. Either a for loop, or a while loop, is OK. Whichever loop makes more sense to you, is fine.

Later, we'll show you how this can be done in much less time, but for now, concentrate on getting a program in loop (and you, thinking in loops), and getting an accurate program.

The best place to start is to work out how to determine if a number is a prime

There are a lot of different ways of doing it, but a good way to start is to use real examples

Is the number 15 a prime number? is the number 17 a prime number?
What did you do to work these out?

Can 15 be divided by 2? No
Can 15 be divided by 3? Yes -> Not a prime

Can 17 be divided by 2? No
Can 17 be divided by 3? No
Can 17 be divided by 4? No
... What number would you stop checking?

It is SO important to be formilar with what the background of what your program needs to achieve.
A lot of problems out there have shortcuts and faster algorithms, and if you don't find them, you are making
a slow algorithm.
Have a look at this page for the answer of what number to stop at: Prime number - Wikipedia, the free encyclopedia

Can this be a loop?
i=2
Can 17 be divided by 'i'? No
i = i + 1
Can 17 be divided by 'i'? No
i = i + 1
Can 17 be divided by 'i'? No
i = i + 1
...

What number would you stop 'i' at and say that there are no divisors? If there are no divisors, it must be a prime.