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?
Thanks in advance.
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.
That should give you a good start.Code:for(int i = 0; i < TestNumber; i++) { if(TestNumber % i == 0) { //The number is not prime } }
Don't quote me on that... ...seriously
OK here is what I have now
For some reason, I am not getting correct calculations.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); }
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
Can someone please help me with what I'm doing wrong?
Thanks
In the IsPrime() function, all_div is wrong.
Change
toCode:all_div = sqrt((double)num);
That will fix your problem.Code:all_div = num/2;
Don't quote me on that... ...seriously
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.
Last edited by 1rwhites; 10-20-2005 at 03:58 PM.
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.
Hope is the first step on the road to disappointment.
if(num % all_div == 0)
result = FALSE;
This should be
if(num % div == 0)
result = FALSE;
Don't quote me on that... ...seriously
Solution : Prime Number
Hi ,
Gone thru your code...... A small change is required as follows
1) Change the following if loop (result = FALSE) part
2) Change the lineCode:if(num % all_div == 0) to if(num % div == 0) { result = FALSE; break; }
It should work....Code:all_div = sqrt((double)num); to all_div = (int)sqrt((double)num);
Have a nice day
It's not like googling "prime number algorithm" returns 0 results or anything.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
OK here is my code now.
but i'm still getting this as my dataCode:#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); }
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
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
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Ok everything is good. thanks everyone for your help.
