Difference between revisions of "Talk:Prime number"

Revision as of 13:36, April 24, 2009

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)

This is only sort of correct. To do it that way makes a proof by contradiction when you would otherwise have a constructive proof. This is suboptimal. JoshuaZ 13:58, 23 April 2009 (EDT)

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 , they differ e.g., on : here 3 is irreducible, but not a prime, as --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)

Sieve of Eratosthenes

The current illustration is - at least - misleading. I made the following table, which is an actual sieve for the numbers 1 - 100. Could it be included?

(yes, I added an h in the name, sorry ) Clement ♗ 09:36, 24 April 2009 (EDT)