Talk:Prime number

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)

Flaw in proof

"It is easy to prove that there are an infinite number of primes using Euclid's second theorem. If there were a finite number of primes, you could multiply them all together and add 1. The resulting number would show the existence of a new prime, since it would not be divisible by any smaller prime (it would always have a remainder of 1)." This argument doesn't work. 510511 = 2 * 3 * 5 * 7 * 11 * 13 * 17 + 1, but it's not prime. Sepura 13:21, 20 February 2008 (EST)

You misunderstand the argument. Since you multiplied only the first 7 primes to get 510510, your hypothesis (the thing to be contradicted in this proof by contradiction) is that those 7 numbers constitute the complete finite set of primes. And in fact, 510511 is not divisible by any of them. Therefore they are not the complete set of primes. And the same argument can be made for any hypothesized finite set. Therefore, no finite set can be the complete set of primes. Ga ohoyt 20:15, 20 February 2008 (EST)