We have x
Divide by numbers between 2 and x
Only need to go to sqrt x
Don’t need to divide by even numbers other than 2
algorithm for checking if number is a prime
loop up dividing number from 2
if divides, add factor list and divide target number by that
stop when i reaches number
eg for 45
divide 2? no
divide 3? yes :> 15
divide 3? yes :> 5
divide 4? no
divide 5? yes :> 1
6>1 so stop
number is prime if list just contains target
don’t have to worry about including non primes in list, as will already have divded by that amount
Identify the integer as the difference of two squares, and use this.
\(x=a.b\)
We use the midpoint of the two as \(c=\dfrac{a+b}{2}\)
This only works for odd numbers. If we have
The we have:
\(a=c+d\)
\(b=c-d\)
\(x=(c+d)(c-d)\)
\(x=c^2-d^2\)
We can test this by trying \(a\) to get \(a^2-x\), and seeing if this is a square number.