Primes and Factors Flashcards
Is “1” considered to be prime?
No, 1 is not prime because by definition a number should be divisible by two factors, by 1 and itself.
Naive way to check for prime?
Naive way is to go from 2 -> n - 1 and see if number is divisible by any number. If so then it is not prime, else prime.
Why checking till n/2 sufficies when checking for prime?
Because there cannot be any factor after n/2 which is equal to n. Lets assume x is a factor, x > n / 2. Now lowest natural number that can be multiplied is 2. So n/2 * 2. So 2 * x > n, and 2 is the smallest value we can multiply. So there cannot be any factor of n after n/2.
Which sieve is famous for prime finding?
Sieve of erastothenes
Explain sieve of erastothenes
Taking 2, we discard all multiples of 2 in range of 1 -> n, like 4, 6, 8, 10, 12 as they cannot be prime as they are divisible by 2. Similarly we do for 3, …
What can be said about factors of a number and pairs?
Factors appear in pairs. if a divides n, then there is a b which also divides n. Like b = a/n. So (a,b) both are factors of n.
Time complexity of sieve of erastothenes?
To be updated.
Example of prime sieves
Sieve of erastothenes, To be updated.
What are co-factors?
b = n/a.If n is divisible by a, then it will also be divisible by a. because a * b = n. Then (a,b) are called co-factors of a number.
Better way than naive way to find primality? Hint sqrt(n).
Given a and b are co-factors of n. a * b = n.
1) If a == b => a^2 = n => a = b = sqrt(n).
2) If a < b => a < sqrt(n) => b > sqrt(n).
3) If b < a => b < sqrt(n) => a > sqrt(n).
So we can say that if we cannot find a factor till sqrt(n), then we will not find any factors after it.
Take example of 36 and plot all factors on number line to visualize.
Prove that there cannot be two factors after sqrt(n) or when reaching sqrt(n), by way of co-factors we have definately seen all factors.
[SELF PROOF - Proof derived by me]
Given n a positive number and sqrt(n). The next smallest number after sqrt(n) will be sqrt(n + 1).
If sqrt(n) and sqrt(n + 1) are co-factors, then
n = sqrt(n) * sqrt(n + 1)
We know that sqrt(n) < sqrt(n + 1)
So,
n < sqrt(n) * sqrt(n)
But sqrt(n) * sqrt(n) = n.
Hence,
n < n. But n cannot be less than n. So by way of refutation we prove that there cannot be two new factors after sqrt(n).
Prove that there cannot be a factor of N after N/2 other than N.
[SELF PROOF - Proof derived by me]
Given N a positive number, the next smallest number after N/2 is (N + 1)/2.
N = x * (N + 1) / 2
Now smallest value of x can be 2. So taking that
N = 2 * (N+1)/2
N = N + 1. But that cannot happen.
What is prime factorization?
Prime factorization is writing factors of a number only in form of primes. For example prime factorization of 24 will be
24 = 2 * 2 * 2 * 3
How many prime factorization can be possible?
ONE. There can only be one prime factorization of a number.
Define Goldbach’s conjecture
Any even number greater than 2, can be expressed as sum of two primes.
