Primality test using a sieve (Prime Adventure part 5)

Channel:
Canada Art of the Problem
Subscribers:
175,000
Published on ● Video Link: https://www.youtube.com/watch?v=f4Gd_vhe_SU


Duration: 5:22
13,534 views
58

An attempt at an optimal trial division primality test using the Sieve of Eratosthenes. We visualize the time complexity of storing all primes up to square root of n and then testing each one. Finally we ask: why can't we just store a precomputed list of primes in memory?



Other Videos By Art of the Problem


2012-12-03Discovery of Magnetic Fields
2012-12-03Discovery of Magnetism
2012-11-30Discovery of the Visible Spectrum
2012-11-29What is Computer Memory?
2012-11-24Discrete Logarithm Problem
2012-11-24Euler's Totient/Phi Function (step 4)
2012-11-22Information Theory part 2: History of the Alphabet
2012-11-08Discovery of Electrostatics
2012-11-02Prime Number Theorem: the density of primes (Prime Adventure part 6)
2012-10-21Sieve of Eratosthenes (Prime Adventure part 4)
2012-10-21Primality test using a sieve (Prime Adventure part 5)
2012-10-14Information Theory part 1: Origins of Cuneiform & Hieroglyphics
2012-10-04Animated history of the letter A (Aleph)
2012-09-26Algorithmic Efficiency (Prime Adventure part 3)
2012-09-26What is a computer? (Prime Adventure part 2)
2012-09-14What is Information Theory? (Information Entropy)
2012-09-11Computational Number Theory (Prime Adventure part 1)
2012-07-30Public key cryptography - Diffie-Hellman Key Exchange (full version)
2012-07-30Public Key Cryptography: RSA Encryption Algorithm
2012-07-29Gambling with Secrets: 8/8 (RSA Encryption)
2012-07-25Information Theory - Teaser


Tags:
primality test
number sieve
sieve
trial division