If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# Primality test with sieve

An attempt at an optimal trial division primality test using the Sieve of Eratosthenes. Created by Brit Cruise.

## Want to join the conversation?

• How can there be a memory limitation to future hardware? Won't computers just keep on getting more advanced as time passes?
• If eventually, I were fortunate enough to store bits on individual electrons with spin, I would still need some atoms to hold the bits. It gets difficult for me to store more than a few or a few dozen bits per atom. So I could estimate my number of bits using a small linear multiple of the number of atoms I used. I would be unable to store more information than I could promptly reach in my ideal shoebox full of carefully-coded atoms. Huge amounts of information would require large blocks of matter. For a list of all primes up to 100,000 digits; I may exceed the mass of a small star. There is not much hope that humans will get more clever than we have here dreamed. Here's my future memory limitation.
• what is n in the video and were can i get more help
• n is just the upper limit. If we are looking for primes up to 100 then n = 100
• Are you saying you can't use machine learning?
• Machine learning would not be an effective technique in finding primes. If you trained it on a large set of numbers, you would, in all likelihood, end up with it learning all the primes below 100, and then guessing that all numbers > 100 that aren't divisible by 2,3,5,7,11,13 are prime, as that would be true a very high percent of the time. So, you'd get something that usually guessed correctly (high percentage of the time), but there would also be an infinite amount of numbers it would guess incorrectly.

Of course, we could achieve that same result in a few lines of code, and skip the lengthy training period for the machine learning.
(1 vote)
• How many primes can one Petabyte hold?
• Can negative numbers be prime or composite, or can only integers be prime or composite?
(1 vote)
• By definition, only integers > 1 may be prime or composite
• What’s about Fermat primality test? I hope you answer my question?
(1 vote)
• The Fermat primality test can also be used to check if a number is prime, however, it is a probabilistic test, (unlike the number sieves). This means that there is a chance that the test is incorrect and might identify a composite number as prime.
• Isn't there a infinite amount of primes? When and how will we get such technology to store all these numbers?
(1 vote)
• Yes, there are infinite primes, so we can't store all of them at once.