# /!\help In C Please /!\

Discussion in 'Programmer's Corner' started by !!Miss.EE!!, Apr 2, 2008.

1. ### !!Miss.EE!! Thread Starter Active Member

Oct 17, 2007
38
0
Hi

How are u all ^__^

I have an assignment that asks to write a function that determines if a number is prime and following questions ....

but untill know the programm doesn't want to work !!!

my question is that ...

the prime funtion is divisible only by one and itself ... thus the reminder must equal either the number it self or 0 ...

OK trying to write this in C whiten my hair ...

so please any one can explain more for me

Regards

2. ### hgmjr Moderator

Jan 28, 2005
9,030
214
Can you provide a flowchart of your prime number algorithm? Then maybe we can give you some suggestions on how it might be improved.

hgmjr

Mar 11, 2008
18
0

4. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
A prime number is one that is divisible only by one and itself.

When you check a number to see whether it's prime, you need to divide the number by all primes up to the integer closest to and less than the square root of the number. For example, to check 39, you would need to divide by 2, then 3, and then 5. (The square root of 39 is 6 plus a little bit, but 6 isn't prime, so you can stop at 5.) You need a loop to do these divisions, one iteration per division.
Mark

5. ### Â¥Ã¶K'Å¾y Member

Mar 27, 2008
19
0
Use modulus fuction to divide your number one by one.
ex:
int mod,flag=0; //mod is the input number;
scanf("%i",mod);
for (int i=1;i<=mod;i++)
{
if(mod%i==0)
{
flag++;
}
}
if(flag==2) //prime number ONLY divisible by one and itself
{
printf("%i is a prime",mod);
}

That's it. it's that simple... ^^

6. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
Any arguments in scanf appearing after the format string have to be addresses.
What you need is
Code ( (Unknown Language)):
1.
2. scanf("%i", &mod);
3.
Aside from that, there is no need to loop through every integer from 1 to mod. At the minimum you can omit every even integer larger than 2, since it is guaranteed not to be prime.
Mark

7. ### Â¥Ã¶K'Å¾y Member

Mar 27, 2008
19
0
Yup, my bad, its a typo... Since I type it manually...

What about 9??? If you just use every even integer then 9 would be a prime too right??

8. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
No, I'm NOT saying that after you eliminate the even integers larger than 2 you'll be left only with primes. There are lots of odd nonprimes: 9 (as you pointed out), 15, 21, 27, ...
But if you eliminate the even integers right off the bat, you essentially double the speed of your routine.

9. ### sixstringartist Member

Apr 8, 2008
18
0
People approach programming in different ways but it is generally a good idea to solve the program on paper (flowchart) before starting to code.

As Mark44 has explained, you can do a special case check for divisible by 2 and then omit other even numbers. Another optimization would be to omit any number above 1/2 of the number you are evaluating.

10. ### Â¥Ã¶K'Å¾y Member

Mar 27, 2008
19
0
Oh I see.. I'm confused when you say "there is no need to loop"....

11. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
¥öK'žy,
I'm not sure whether you're still confused, or if my explanation cleared it up. In case you still are confused, the code you showed earlier in this thread has a for loop that runs through all the integers from 1 to mod, the number you're checking whether it's a prime. Going back to the example I gave earlier, if you're checking 39, it's very inefficient to check every integer from 1 to 39. It's sufficient to divide only by 2, 3, and 5. You don't need to go all the way to half of 39 (or 19) , as sixstringartist said--you can quit at the greatest odd integer less than sqrt(39), or 5. I hope that's clear.

12. ### Kelth Member

Mar 4, 2008
12
0
Couldn't one just divide the number by say 2 through 9 and if it is divisible then it is not prime; and if not, then it is prime? Since I believe that any non-prime natural number is dividable by a natural number between 2 and 9.

13. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
Sorry, but that won't work. A counterexample to your statement is 143. It's not divisible by 2, 3, 5, 7, or 9, but it's not prime.

If every nonprime were divisible by an integer between 2 and 9, then public key encryption absolutely woudn't work. The basis of this encryption algorithm is a very large composite number (i.e., nonprime) made up of two large prime factors. The numbers involved are so large that it takes even the current generation of computers an inordinate amount of time to break them into their prime factors.
Mark

14. ### Â¥Ã¶K'Å¾y Member

Mar 27, 2008
19
0
Yeah that's clear me enough.
Just never thought if we can quit at the greatest odd integer less than the sqrt of the integer.
Thanx.

15. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
Here's how that works.

Suppose you have a number n that is not prime. There are two possibilities: it's a perfect square (like 36 or 81), or it's not.

Case 1. n is a perfect square
Two of the factors, clearly are $\sqrt{n}$ and $\sqrt{n}$, and both of these are integers.

Case 2. n is not a perfect square
Since n is not a perfect square, $\sqrt{n}$ is not an integer. Because we're assuming that n is not a prime, it must have integer factors a and b, where a*b = n. Necessarily one of these factors, call it a, is smaller than $\sqrt{n}$. The other factor, call it b, has to be larger than $\sqrt{n}$.

Here's an example. Let n = 65. Since the $\sqrt{65}$ is a little larger than 8, we don't need to check any numbers larger than 8. In fact, we only need to check up to 7.

If I divide by 2, I get a remainder.
If I divide by 3, I get a remainder.
Skip 4.
If I divide by 5, there's no remainder, which says that 5 is a factor.
Skip 6.
If I divide by 7, I get a remainder.

I could go all the way up to 65/2, or 32 (rounding down), as someone suggested earlier, but any checks past 7 are a waste of time. The next number that divides evenly is 13, but I could have figured that out, since I already knew that 5 was a divisor (5 * 13 = 65).

Notice that 5 < $\sqrt{65}$ and 13 > $\sqrt{65}$, in agreement with what I said earlier.

Mark

Mar 27, 2008
19
0