Prime number by considering Time complexity

 

1 2 3 4 5 6 7 8 9 10

function isPrime(val) { if(val<=1) console.log('Not a Prime Number'); for(var i=2; i<val ; i++) { if(val%i==0) return false; } }

Time Complexity: O(n)

The time complexity is O(n) because this algorithm checks all numbers from 0 to n.

Questions to ask ourselves :

1. Is it possible to find a pattern and make the algorithm faster? 

2. Is more optimization possible?

The answer is yes,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

function isPrime(n) { if(n<=1) return false; if(n<=3) return true; if(n%2==0 || n%3==0) return false; for(var i=5; i*i<=n ; i=i+6) { if(n%i==0 || n%(i+2)==0) return false; } return true; }

Time Complexity: O(sqrt(n))

In case if we want to print all prime numbers upto "n", in addtion to the above logic, we need to use below code.

1 2 3 4 5 6 7 8 9 10

function allPrimes(n) { for(var i=0; i<n; i++) { if(isPrime(i)) { console.log(i+', '); } } }

Time Complexity: O(sqrt(n)) + O(n) = O(n sqrt(n)).