If I want to calculate all the primes, could I do this? Let $N = \{2,3,4,5,6,7,8,..\}$ Then the elements in $N - NN$ are prime? Because they are the ones that aren't composite?
Asked
Active
Viewed 194 times
4
-
1What is $NN$? And what is $N-NN$? – Asaf Karagila Jun 10 '15 at 17:39
-
NN is the set product, and N - NN is all the elements in N which are not contained in NN. – Jun 10 '15 at 17:39
-
3This is what's in action in Eratosthenes's sieve. – Bernard Jun 10 '15 at 17:40
-
@bernard but in a very effective way! Deleting the numbers sequentially is very slow. – Peter Jun 10 '15 at 17:41
-
Who's more effective? Our old friend Ἐρατοσθένης? – Bernard Jun 10 '15 at 17:44
-
2It seems to me it's only theoretically faster. You first have to set up the list of all products of two numbers. – Bernard Jun 10 '15 at 17:46
2 Answers
4
Yes, that is correct.
If $m$ is a composite, then it can be written as $n\cdot k$ for some $2\leq n,k<m$, which means that $m\in NN$.
If $m$ is a prime number, then it cannot be written as such product, so it is not in $NN$. Therefore $N-NN$ is exactly the prime numbers.
Asaf Karagila
- 393,674
2
Essentially, yes. You may struggle to compute $N-NN$, but that set would contain the primes and only the primes.
If you want to actually calculate prime numbers, a good way would be to use the Sieve of Eratosthenes (the animation uses $n=10$). The idea is you start with a list of primes up to some number $n$, and then consider the integers up to $n^{2}$. Every composite number in this interval must have at least one prime factor at most as large as $n$, so if you eliminate all the multiples of primes up to $n$, you have all the primes up to $n^{2}$.
preferred_anon
- 17,121