Is Prime Help

[Jaxyral]

I am making a program that takes user input and then returns either true of false based on whether the number entered is prime. Prime = True, Not Prime = False. I am having trouble with the red colored code that follows. More specifically. The math is correct i think but I'm missing something.

<script type="text/javascript">

function frontWork() {
var n = parseFloat(document.getElementById("inBox").value);
var output = isPrime(n);
document.getElementById("outBox").value=output;
}

function isPrime(n) {
if (n == 1 || n == 2){
return true;
}

for (var i=2;i<n;i++) {
if (num &#37; i == 0) {
return true;
break;

}
if (n % i != 0) {
return false;
}
else {
return true;
}
}
}
</script>

[Charles]

You've a syntax error there--and you're making things more difficult than you need.

Number.prototype.isPrime = function () {
	var n = Math.abs (this);
	for (var i = 2; i < n; i++) if (n &#37; i == 0) return false;
	return true; 
}	

n = Number (prompt ('Number', '')); 
alert (n.isPrime() ? 'Prime' : 'Not prime');

[Y_Less]

That can be optimised as numbers above the root of a number are only factors if a number below the root is a factor too (as they will be multiplied together):

Number.prototype.isPrime = function ()
{
	var
		n = Math.abs(this), m = Math.sqrt(n), i = 1;
	while (++i <= m)
	{
		if (!(n &#37; i))
		{
			return false;
		}
	}
	return true; 
}

n = Number (prompt ('Number', ''));
alert (n.isPrime() ? 'Prime' : 'Not prime');

[Declan1991]

And you can immediately reduce the number of modulus tests by half if you test for two separately. You can do the same trick indefinetly obviously, but it's most efficient for two IMO.

function isPrime(n) {
    n = Math.abs(n);
    var l = Math.sqrt(n);
    if (n%2) return false;
    for (i = 3; i < m; i += 2) {
        if (!(n % i)) {
            return false;
	}
    }
    return true; 
}

Also, using closures, if generating a list of primes, you can store the primes already found in an array, and you only have to test the next number with those primes up to the square root of the number, a very efficient way to generate a list of primes. Also, you can use facts like, all primes will either be 6n + 1 or 6n - 1 to speed up the process.

[Kor]

Watch out the typo! :

function isPrime(n) {
    n = Math.abs(n);
    var l = Math.sqrt(n);
    if (n%2) return false;
    for (i = 3; i < m; i += 2) {
        if (!(n % i)) {
            return false;
	}
    }
    return true; 
}

[Declan1991]

function primes(n) {
	n = Math.abs(n);
	if (n%2==0 || n%3==0)
		return false;
	for (var i = 6, l = Math.sqrt(n)+1; i < l; i+=6) {
		if (n%(i+1) == 0 || n%(i+1) == 0) {
			return false;
		}
	}
	return true;
}

That's the one I've been using recently. Quickest I know bar functions for generating primes.

[Y_Less]

Why do you do an or with two identical conditionals?

[Declan1991]

What is with my typos in this thread!

function primes(n) {
	n = Math.abs(n);
	if (n%2==0 || n%3==0)
		return false;
	for (var i = 6, l = Math.sqrt(n)+1; i < l; i+=6) {
		if (n%(i+1) == 0 || n%(i-1) == 0) {
			return false;
		}
	}
	return true;
}

[mrhoo]

Something's not right with Declan's code-
it returns true for the following non-prime numbers:
1, 2, 3, 25, 121, 289, 529, 841, 1681, 2209, 2809, 3481, 5041, 6889, 7921, 10201, 11449, 12769, 17161, 18769, 22201, 27889, 29929, 32041, 36481, 38809, 51529, 54289, 57121, 63001, 66049, 69169, 72361, 78961, 85849, 96721

Both of your functions call 0 and 1 prime numbers, as well as most decimals and negative numbers, which cannot by definition be prime.

I stick with Erotosthenes, who wrote this for an earlier form of javascript :

Number.prototype.isPrime= function(){
    if(this== 2) return true;
    var n= Math.floor(this);
    if(n!= this || this< 3 || !(this&#37;2)) return false;

    var i= 3, limit= Math.sqrt(n)+1;
    while(i< limit){
        if(!(n%i)) return false;
        i+= 2;
    }
    return true;
}

Half the code is to check for special cases- numbers less than 3 or divisible by 2 that are not 2, and non-integers.

In mathematics, a prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself

There are two conventions for the set of natural numbers: it is either the set of positive integers {1, 2, 3, ...}
according to the traditional definition or the set of non-negative integers {0, 1, 2, ...}

[Declan1991]

Ah I see my problem, I was trying prime generator trick (all primes are in the form 6n+-1) to reduce the number of division tests I had to use. Obviously it doesn't work.

And, by the way, 2 and 3 are prime.

If anyone is interested, this is the principle I mistakenly tried to implement (using JavaScript v1.8's generator functions). That definetly works because I have used it, and didn't have to alter it.

function primes() {
	yield 2;
	yield 3;
	let p = [2,3], flag;
	for (let n = 6;; n+=6) {
		flag = true;
		let s = Math.sqrt(n)+1, t = n-1;
		for (let i = 0; p[i]< s; i++) {
			if (t&#37;p[i] == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			yield t;
			p[p.length] = t;
		}
		flag = true;
		t = n+1;
		for (let i = 0; p[i]< s; i++) {
			if (t%p[i] == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			yield t;
			p[p.length] = t;
		}
	}
}

[mrhoo]

It is strange that it almost worked- there are 9592 primes below 100,000 and your method correctly identified
all the intergers that are prime (yes, including 2 and 3 and only mis-called those 20 odd.

[Declan1991]

I figured it out. The problem was square numbers (in particular (6n-1)^2). Take 25. The square-root plus one is 6. The for loop then wouldn't run, which let it through. This code (or I presume using i <= l instead of <) works for sure. And this time I tested on numbers that weren't prime as well as those that are .

function isPrime(n) {
	n = Math.abs(n);
	if (n == 2 || n == 3) return true;
	if (n&#37;2==0 || n%3==0 || n < 3) return false;
	for (var i = 5, l = Math.sqrt(n)+1; i < l; i+=6) {
		if (n%(i) == 0 || n%(i+2) == 0) {
			return false;
		}
	}
	return true;
}

I was trying to get a more efficient function, but that's probably negligible. The loop is slightly refractored, and for big numbers, it only has 2/3 of the modulus tests to do, but it has more to do initially.

[mrhoo]

Thank you for catching that, Declan, and explaining it- a method that works 99 percent of the time drives me nuts- I hadn't unraveled the squares yet. Nice job.

[Declan1991]

I was getting worried, I'd posted three functions in this thread, and none worked!

[Kor]

Here's a development (written by rnd me), following your idea:


Number.prototype.isPrime

(function(){function isPrime(){ var n=this;
	if(isPrime[n]){ return true; }
	if( n<11|| ! ((n&#37;2)&&(n%3)&&(n%7)&&(n%9)) ){ return false; }
	for (var i=5, l=Math.sqrt(n)+1; i<l; i+=6){
		if( !(n%i) || !(n%(i+2)) ){ return false; }
	}
   return isPrime.n++ < 1e6 ? (isPrime[n]=true) : true;
}; var p=isPrime;p.n=0;p[2]=p[3]=p[5]=p[7]=true; Number.prototype.isPrime=p;
}());