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)

Why Mathematicians Prefer the Alternative Definition

Because mathematician make a distinction between irreducible elements (p irred. <=> (a|p => a unit or a=p)) and prime elements (p prime <=> (for all a,b: p|ab => p|a or p|b). While these two properties coincide on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{Z}} , they differ e.g., on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{Z}[\sqrt{-5}]} : here 3 is irreducible, but not a prime, as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 21 = 3 \cdot 7 = (1 + 2 \sqrt{-5})(1 - 2 \sqrt{-5})} --DiEb 13:03, 29 August 2008 (EDT)

NP Complete

Please fix the incorrect statement about the NP-completeness of prime factorization. In fact, prime factorization is known not to be in NPC unless P=NP. --DiogenesTonne 17:59, 22 April 2009 (EDT)

Since this article is currently protected...

You can't have an article on primes that discusses primality testing and doesn't mention Agrawal's algorithm. There needs to be a mention of the AKS test which allows primality testing in polynomial time. This was a big deal. JoshuaZ 20:49, 22 April 2009 (EDT)

Suggested addition: In 2002 Manindra Agrawal, Neeraj Kayal, and Nitin Saxena constructed an algorithm that determined primality in polynomial time. This algorithm was based off of a generalization of Fermat's Little Theoren.[1]

How's that for starters? JoshuaZ 12:50, 23 April 2009 (EDT)