Numbers > 0 which are divisible by 1 and itself. Example: 2,3,5,7,11..
Facts about prime numbers:
- Every prime number can be represented in form of (6n+1) and (6n-1) except 2 and 3, when n > 0.
- 5 : (6 * 1 ) -1, 29: (6 * 5) - 1
- 2 and 3 are only two consecutive natural numbers, which are prime too.
- 1 is neither prime nor composite.
check if a number is prime or not
Naive approach:
- If, N < 2. It is not prime, return False.
- Else: Iterate from 2 to N-1 and check if any of the numbers between 2 and N-1 (both inclusive) divides N or not. If yes, then N is not prime, return False. Otherwise, return True.
1bool isPrime(n){
2 if(n<2) return false;
3 for(i = 2 i<= n; i++){
4 if(n%i==0) return false;
5 return true;
6 }
7} //TC : O(n-2) SC: O(1)
A better approach:
- Divisors always appear in pairs.
- 30: (1,30),(2,15), (3,10),(5,6)
- if x,y is a pair then (x * y) = n
- if x < =y , x^2 = n, x = sqrt(n).
- we dont need to traverse numbers from 1 to n, just traverse from 2 to sqrt(n)
1bool isPrime(n){
2 if(n<2) return false;
3 for(i = 2 i * i<= n; i++){
4 if(n%i==0) return false;
5 return true;
6 }
7} //TC : O(sqrt(n)) SC: O(1)
Max efficient method (for large values of ‘n’) :
We can save many iterations for large ‘n’ by checking if n % 2==0 and n%3 ==0. If we check for these two we dont need to check for multiples of 2 and 3.
1bool isPrime(n){
2 if(n<2) return false;
3 if(n==2 || n==3) return true;
4 //optimisation: skip multiples of 2 and 3
5 if(n%2==0 || n%3==0) return false;
6 // here i (will be) i = 5,7,11,17,23,29...
7 for(i = 5; i * i<= n; i += 6){
8 if(n%i==0 || n%(i+2) ==0) return false;
9 return true;
10 }
11}
Prime Factors
print all prime factors of n.
Input: n =12
Output: 2,2,3.
Input: n =13
Output: 13.
Input: n = 315
Out: 3,3,5,7
Naive approach:
1void primefactors(int n){
2 for(i = 2; i <=n ;i++){
3 if(isPrime(i)){ //TC: O(sqrt(n))
4 int x = i;
5 while(n%x==0){
6 cout << i << endl;
7 x = x*i;
8 }
9 }
10 }
11} //total TC ::O(n^2 logn)
Efficient solution:
- Divisors always appear in pairs. (If we traverse from 2 to sqrt(n) we get a prime divisor)
- let (x,y) be a pair. x * y = n.
- if x<=y, x *x <=n, x <= sqrt(n)
- let (x,y) be a pair. x * y = n.
- A number ‘n’ can be written as multiplication of power of prime factors
- 12 = 2^2 * 3
- 450 = 2 * 3^2 * 5^2
1void primefactors(int n)
2{
3 if (n <= 1)
4 return;
5 for (i = 2; i * i <= n; i++)
6 {
7 while (n % i == 0)
8 {
9 printf(i);
10 n = n / i;
11 }
12 }
13 if (n > 1)
14 printf(n) //cornercase : if our last(largest prime factor is of power 1 -> specify it explicitly )
15}
Further optimisation:
- Take out multiples of 2 & 3 out. If num is divisible by 2 then dont check with multiples of 2. same with 3.
1const primefactors = (n) => {
2 if (n <= 1) return;
3 while (n % 2 == 0) {
4 console.log(2);
5 n = Math.floor(n / 2);
6 }
7 while (n % 3 == 0) {
8 console.log(3);
9 n = Math.floor(n / 3);
10 }
11 for (let i = 5; i * i <= n; i += 6) {
12 while (n % i == 0) {
13 console.log(i);
14 n = Math.floor(n / i);
15 }
16 while (n % (i + 2) == 0) {
17 console.log(i);
18 n = Math.floor(n / (i + 2));
19 }
20 }
21 if (n > 3) console.log(n); //cornercase : if our last(largest prime factor is of power 1 -> specify it explicitly )
22}; // TC: O(sqrt(n))
Divisors of a number
Print all divisors of number ‘n’ in increaasing order. Eg: n= 5 -> 1,3,5,15. n = 100 -> 1,2,4,5,10,20,25,50,100
Naive approach:
1function divisors(n) {
2 for (let i = 0; i < n; i++) {
3 if (n % i == 0) console.log(i);
4 }
5} //TC: O(n), SC: O(1)
Efficient solution:
- Divisors always appear in pairs.
- One of the divisors in every pair is smaller than or equal to sqrt(n)
- if x,y is a pair then (x * y) = n
- if x < =y , x^2 = n, x = sqrt(n).
- if x,y is a pair then (x * y) = n
- If we traverse from 1 to sqrt(n) we will find atleast one divisor of sqrt(n).
This approach doesn’t print output in sorted order..
1const divisors = (n) => {
2 let i;
3 for (i = 1; i * i < n; i++) {
4 if (n % i == 0) console.log(i);
5 // for perfect squares case
6 if (i != Math.floor(n / i)) console.log(n / i);
7 }
8}; // TC: O(sqrt(n))
To get output in sorted order..
1const divisors = (n) => {
2 let i;
3 for (i = 1; i * i < n; i++) {
4 if (n % i == 0) console.log(i);
5 }
6 for (; i >= 1; i--) {
7 if (n % i == 0) console.log(n / i);
8 }
9}; // TC: O(sqrt(n) + sqrt(n)) => O(sqrt(n))
- Outer for loop traverses from 1(inclusive) to sqrt(n)(exclusive).
- Inner for loop runs from sqrt(n) (inclusive) to sqrt(n) (exclusive)
Sieve of Eratosthenes
Print all primes < n. Eg :n = 10 => 2,3,5,7. n = 23 => 2,3,5,711,13,17,19,23
This is the most efficient way of generating prime numbers upto a given number N.
Algorithm:
- Create a boolean array of size n+ 1 wih all values filled with true.
- Leave the first two cells 0 & 1 as (0 & 1 are not primes)
- Mark multiples of prime numbers to be false in the array.
- Print out remaining true values
1const sieve = (n) => {
2 if (n <= 1) return;
3 let isPrime = new Array(n + 1);
4 isPrime.fill(true);
5 // if i is true, mark all of its multiples as false
6 for (let i = 2; i * i <= n; i++) {
7 if (isPrime[i]) {
8 for (let j = 2 * i; j <= n; j = j + i) {
9 isPrime[j] = false;
10 }
11 }
12 }
13 //print all primes from the array
14 for (let i = 2; i <= n; i++) {
15 if (isPrime[i]) console.log(i);
16 }
17}; //TC: O(nloglogn)
A small optimisation..
1const sieve = (n) => {
2 if (n <= 1) return;
3 let isPrime = new Array(n + 1);
4 isPrime.fill(true);
5 // if i is true, mark all of its multiples as false
6 for (let i = 2; i * i <= n; i++) {
7 if (isPrime[i]) {
8 for (let j = i * i; j <= n; j = j + i) {
9 isPrime[j] = false;
10 }
11 }
12 }
13 //print all primes from the array
14 for (let i = 2; i <= n; i++) {
15 if (isPrime[i]) console.log(i);
16 }
17}; //TC: O(nloglogn)