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

 

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

 

Look up the modulus operator. Your answer lies there.

 

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

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

 

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... ^^

 

scanf("%i",mod);

Any arguments in scanf appearing after the format string have to be addresses.
What you need is

scanf("%i", &mod);

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

 

Any arguments in scanf appearing after the format string have to be addresses.

Yup, my bad, its a typo... Since I type it manually...

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

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

 

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.

 

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.

 

Oh I see.. I'm confused when you say "there is no need to loop"....

 

¥ö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.

 

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.

 

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

 

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.

 

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

 

Thanx for the explanation. I've already try it with the calculator before read your reply T_T. And its true. thanx again.