# for loop to find prime numbers

This is a discussion on for loop to find prime numbers within the C Programming forums, part of the General Programming Boards category; For my program, I need to check whether a number is prime or not. I have to use a for ...

1. ## for loop to find prime numbers

For my program, I need to check whether a number is prime or not. I have to use a for loop. And I only have to check for divisors that are less then or equal to the square root of the number being tested. Does anybody know how to do this?

2. Just run the for loop. With every cycle take the number you are testing and check for remainders when you divide by the number the for loop is on.

Code:
```for(int i = 0; i < TestNumber; i++)
{
if(TestNumber % i == 0)
{
//The number is not prime
}
}```
That should give you a good start.

3. OK here is what I have now

Code:
```#include <stdio.h> /* define fopen,fclose,fscanf,fprintf */
#include <math.h> /* sqrt definition */
#define TRUE 1
#define FALSE 0

int is_prime(int num);

int main(void)
{
FILE *inp,
*outp;

int number;
int input_status;
int finish;

inp = fopen("prime.dat","r");
outp = fopen("prime.out","w");

input_status = fscanf ( inp, "%d", &number);

finish = number;

while (input_status == 1){
if (is_prime(number))
fprintf(outp, " %d is a prime number\n",number);
else
fprintf(outp, " %d is not a prime number\n",number);

input_status = fscanf ( inp, "%d", &number);

}

fclose(inp); /* close files */
fclose(outp);
return(0);

}

int is_prime(int num)
{
int div;
int all_div;
int result;

if (num == 1)
return(FALSE);
else if (num == 2)
return(TRUE);

all_div = sqrt((double)num);

for(div = 2; div <= all_div; div++)
{
if(num % all_div == 0)
result = FALSE;
else
result = TRUE;
}
return(result);

}```
For some reason, I am not getting correct calculations.
Here is what I get when I run it.

50 is a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is a prime number
80 is not a prime number
84 is a prime number
65 is a prime number
61 is a prime number
63 is not a prime number
77 is a prime number

Thanks

4. In the IsPrime() function, all_div is wrong.

Change
Code:
`all_div = sqrt((double)num);`
to
Code:
`all_div = num/2;`

5. Here is my data now.
50 is not a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is not a prime number
80 is not a prime number
84 is not a prime number
65 is a prime number
61 is a prime number
63 is a prime number
77 is a prime number

I'm still getting some wrong data. Any other suggestions?

The way it is right now, it says every even number is not prime and every odd number is prime. But I don't know how to fix that.

6. No, actually using the square root is "more correct". Once you've hit the square root of a number, there's no point in going any higher, because you've already done those. Consider:

1x8
2x4
(square root hits here)
4x2
8x1

The square root check hits before you reach the half way point. This is just a simple illustration, but the point is, the square root of a number will be less than half of a number, and there's no point in checking any further.

Back to the loop...

Anything divisible by 2 is not a square root, so that elminates half of the numbers you'd check. Increment by 2 then, instead of 1. That saves you half the needed calculations.

Quzah.

7. if(num % all_div == 0)
result = FALSE;

This should be

if(num % div == 0)
result = FALSE;

8. ## Solution : Prime Number

Hi ,

Gone thru your code...... A small change is required as follows

1) Change the following if loop (result = FALSE) part
Code:
``` if(num % all_div == 0)   to

if(num % div == 0)
{
result = FALSE;
break;
}
```
2) Change the line
Code:
``` all_div = sqrt((double)num);    to

all_div = (int)sqrt((double)num);```
It should work....

Have a nice day

9. It's not like googling "prime number algorithm" returns 0 results or anything.

10. OK here is my code now.

Code:
```#include <stdio.h> /* define fopen,fclose,fscanf,fprintf */
#include <math.h> /* sqrt definition */
#define TRUE 1
#define FALSE 0

int is_prime(int num);

int main(void)
{
FILE *inp,
*outp;

int number;
int input_status;
int finish;

inp = fopen("prime.dat","r");
outp = fopen("prime.out","w");

input_status = fscanf ( inp, "%d", &number);

finish = number;

while (input_status == 1){
if (is_prime(number))
fprintf(outp, " %d is a prime number\n",number);
else
fprintf(outp, " %d is not a prime number\n",number);

input_status = fscanf ( inp, "%d", &number);

}

fclose(inp); /* close files */
fclose(outp);
return(0);

}

int is_prime(int num)
{
int div;
int all_div;
int result;

if (num == 1)
return(FALSE);
else if (num == 2)
return(TRUE);

all_div = (int)sqrt((double)num);

for(div = 2; div <= all_div; div++)
{
if(num % div == 0)
result = FALSE;
else
result = TRUE;
}
return(result);

}```
but i'm still getting this as my data

50 is a prime number
17 is a prime number
45 is a prime number
19 is a prime number
2 is a prime number
36 is not a prime number
31 is a prime number
41 is a prime number
52 is a prime number
80 is not a prime number
84 is a prime number
65 is a prime number
61 is a prime number
63 is not a prime number
77 is a prime number

11. if(num % div == 0)
result = FALSE;
else
result = TRUE;
You've got to check all the numbers before finally returning TRUE.
Any false is immediate exit from the function.
You only get true if ALL the tests fail

12. Ok everything is good. thanks everyone for your help.