Difference between revisions of "Talk:Prime number"
Jump to navigation
Jump to search
Isaac4given (talk | contribs) (error testing primality of 4) |
|||
| Line 20: | Line 20: | ||
[[User:Isaac4given|Isaac4given]] 11:28, 10 January 2008 (EST) | [[User:Isaac4given|Isaac4given]] 11:28, 10 January 2008 (EST) | ||
| + | |||
| + | I'm surprised that 9 worked. Try. | ||
| + | <blockquote><pre> | ||
| + | for (s = 2; s <= sqrt(N); ++s) { // less than or equal to catch perfect squares | ||
| + | if (N % s == 0) { | ||
| + | printf("N is not a prime number."); | ||
| + | } | ||
| + | } | ||
| + | </pre></blockquote> | ||
| + | |||
| + | [[User:Ga ohoyt|Ga ohoyt]] 13:32, 10 January 2008 (EST) | ||
Revision as of 18:32, January 10, 2008
Primality testing - Problems with the number 4
When testing whether a number N is divisible by s, using values of s from 2 to N - 1, when N is 4, the method correctly determines that 4 is not prime, because it is divisible by 2. This example is in the C programming language.
for (s = 2; s < N - 1; ++s) {
if (N % s == 0) {
printf("N is not a prime number.");
}
}
However, when using values of m from 2 to the square root of n, when n is 4, an error can occur. Since 2 is the square root of 4, the test range is 2 to 2, and, if the range is exclusive, as in a for-loop, the whole test is skipped, and 4 is incorrectly determined to be a prime number.
for (s = 2; s < sqrt(N); ++s) {
if (N % s == 0) {
printf("N is not a prime number.");
}
}
Isaac4given 11:28, 10 January 2008 (EST)
I'm surprised that 9 worked. Try.
for (s = 2; s <= sqrt(N); ++s) { // less than or equal to catch perfect squares
if (N % s == 0) {
printf("N is not a prime number.");
}
}
Ga ohoyt 13:32, 10 January 2008 (EST)