Main content
Computer science
Course: Computer science > Unit 2
Lesson 6: Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Trial division
Define the problem
We need to build a machine which can answer a simple yes/no question. Given an input integer n, is n prime?
Let's think about what would be inside this machine to make it work. Machines can only follow a sequence of steps based on some instructions, known as an algorithm. To warm up, let's find out what algorithm is inside your brain. Answer the following question: is 49 prime?
…
No? How did you do that? You likely searched for a divisor of 49 which is greater than 1 and less than 49. If you haven't memorized your multiplication tables then you'd naturally follow this sequence:
- Does 2 divide 49? NO
- Does 3 divide 49? NO
- Does 4 divide 49? NO
- Does 5 divide 49? NO
- Does 6 divide 49? NO
- Does 7 divide 49? YES
We found a divisor of 49 (7) which is proof that 49 is composite.
Building a wall
However what if I asked you if 2971215073 is prime?
Are you still checking? After the first few thousand tests I still haven't found a divisor. The key question is, when can we stop checking and prove that n is prime? (let's call this our wall) As a starting point, we know our wall must be n-1 (since n divides n). If we check up to 2971215072 either we find a divisor (which proves n is composite) OR we don't (which proves n is prime).
Building a better wall
This would work, but can we move our wall to save time? Remember, that we are actually searching for the first (or smallest) divisor. Sometimes the smallest divisor could be 2, though it could also be much larger. This brings us to the key question: how large could the smallest divisor be?
Remember that any composite integer n is build out of two or more primes n= P * P …
P is largest when n has exactly two divisors which are equal to each other. This is known as a square number such as 9 (9 = 33) or 49 (49 = 77). To capture this worst case scenario we simply build our wall at the square root of n!
Convince yourself of this: if we don't find a divisor of n after checking up to square root of n, then n must be prime. Try to prove this to yourself (a proof is at the bottom of this article)
Trial division algorithm
That's it, we are ready to move on. First let's summarize our trial division algorithm in plain english:
- Accept some input integer n
- For each integer x from {2 ... sqrt(n)} check if x divides n
- If you found a divisor then n is composite OR ELSE n is prime
If you have programming experience you should open a CSscratchpad and try and get this function working. If not, you can proceed to the next step where I have provided a working version for you to use as a starting point. (FYI It is possible to do this lesson without doing any programming).
Want to join the conversation?
if i'm not mistaken, if n is not 2, it could be determined if n is even, in which case it is not prime, and the rest of the process could be avoided, similarly, were this not the case, and the process of trial divisions were continued, all even divisors could be discarded, likely halving the length of process, if i'm correct.(2 votes)
You are correct.
A fairly standard optimization is to:
check divisibility by 2
start trial division from 3, checking only odd numbers
Often we take it on step further:
-check divisibility by 2
-check divisibility by 3
-starting at k=1 check divisibility by 6k-1 and 6k+1
then increment k by 1
(Any integer in the form of 6k+2, 6k+4 is divisible by 2 so we don't need to check them,
Any integer in the form 6k, 6k+3 is divisible by 3 so we don't need to check them,
this leaves only integers in the form 6k+1 and 6k+5 to check. But 6(k+1)-1 is the same as 6k+5, So if we increment k and check 6k-1 we will be checking 6k+5 for the original k )(9 votes)
Because it says if we don't find a divisor of n after checking up to square root of n, then n must be prime, then doesn't that mean that every number which is not a perfect square is a prime?(2 votes)- Here's a simple counter example:
10 is not a perfect square.
10 is not prime.
The square root of 10 is ~3.16
2 is a a divisor of 10
2 <= 3.16
If a number x is not prime we will, like above, find a divisor which is <= sqrt(x)(4 votes)
- a simple trial question and answer for someone without programming background?(3 votes)
I'm not very good at math, this seems very complicated just by me reading this. Is there a more simpler way to solve the problems that could help me understand(2 votes)
Lets look at 26.
The square root of 25 is 5, so the square roots of 26 is 5.09. That means that 5.09*5.09 is 26. If 26 is not a prime number, then each product will include at least one number up to 5.09.
Since we are looking for whole numbers, we are interested in the integers 2, 3, 4, and 5.
Divide the start number, 26, by each of the integers.
26\5 Not an integer
26/4 Not an integer
26/3 Not an integer
26/2=13
Since the product of two integers, 2 and 13, is 26, 26 is not a prime number. If you still do not understand you will want to head over to the math section and put in serious work.(3 votes)
- It is possible code in Python on the scratchpad ?(1 vote)
For the programming part of this, does anyone know how to ask for the square root of a number in processing.js(2 votes)- I wonder if it would be feasible to make some kind of state machine for this using iterative algorithm (to be found) ?
Generating factorisations of subsequent composite numbers seams to be quite regular :
4=2*2
6=3*2
8=2*2*2
9=3*3
10=5*2
12=3*2*2
14=7*2
15=5*3
16=2*2*2*2
18=3*3*2
20=5*2*2
21=7*3
22=11*2
24=3*2*2*2
25=5*5
26=13*2
27=3*3*3
28=7*2*2
30=5*3*2
Checking factorisation of "n" would be just geting already computed close factorised composite <n, generate subsequent factorisations (using the algorithm) until f >n and check if the number is one of generated ... if not - we have a prime.(2 votes) - why isn't it n = p1*p2...*pk >= p1*p1(1 vote)
Here's some "pseudo-code" for anybody who is a bit confused.
To find if N is prime:
Set a variable named index to 2.
Set a variable named result to true.
While index squared is less than or equal to N:
If N is divisible by index:
Set result to false.
Change index by 1.
If result is true, N is prime or less than 2.
If result is false, N is composite.
The reason you only need to check for factors less than or equal to the square root of N is because if you have a factor F that is greater than the square root of N, the factor you multiply with F to get N is less than the square root of N.(1 vote)
Why not just stop the algorithm if the result of the square root of n is an integer ? It would make the algorithm work faster.(1 vote)
yet is it possible?(1 vote)