Primality Test Comparism Javascript

js_primality.md

JAVASCRIPT PRIMALITY TEST (SQRT VS PLAIN)

Demonstrating how two algorithms of the same number of line can be striking different in terms of performance.

I tested both algorithm on repl.it and used the same values for both tests.

The second algorithm:

30313411: true
Time taken: 435ms

The first algorithm:

30313411: true
Time taken: 11ms

You can test for yourself on repl.it using the follow links:

Test Second Algorithm

Test First Algorithm

prime.js

/*
Javascript Primality test
The Naive way.
*/
function isPrime( x ){
	
	if(x < 2)
		return x + ": " + false;
		
		for( var i = 2; i < x-1; i++ ){
			
			if( x % i === 0 )
			
				return x + ": " + false;
			}
			
		return x + ": " + true;
		
}
console.time('Time taken');
console.log(isPrime(30313411));
console.timeEnd('Time taken');

prime2.js

/*
Javascript primality test
A better way.
*/
function isPrime( x ){
	
	if( x < 2 )
		return x + ": " + false;
		
	for(var i=2; i< Math.round(Math.sqrt(x)) + 1; i++){
		
		if(x % i === 0)
		
			return x + ": " + false;
	}
	
	return x + ": " + true;
	
}
console.time('Time taken');
console.log(isPrime(30313411));
console.timeEnd('Time taken');