Uncommon · History
Trial division
Primality test
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than or equal to the square root of n.
From Wikipedia
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than or equal to the square root of n. For example, to find the prime factors of n = 70, one can try to divide 70 by successive primes: first, 70 / 2 = 35; next, neither 2 nor 3 evenly divides 35; finally, 35 / 5 = 7, and 7 is itself prime. So 70 = 2 × 5 × 7. Trial division was first described by Fibonacci in his book Liber Abaci (1202).
Text: Wikipédia, CC BY-SA 4.0. ·
Related cards
-
★★★★
Perfect number
Positive integer which equals the sum of all its divisors
-
★★★
Sieve of Eratosthenes
Ancient algorithm for generating prime numbers
-
R★
RSA Factoring Challenge
Computational number theory challenge aimed at factorizing a given set of semi-prime numbers
-
A★★
AKS primality test
Primality test
-
★
Divergence of the sum of the reciprocals of the primes
Theorem
-
★★
Pentium FDIV bug
Bug in the Intel P5 Pentium floating point unit