
Is Prime Help
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 % i == 0) {
return true;
break;
}
if (n % i != 0) {
return false;
}
else {
return true;
}
}
}
</script>
Last edited by Jaxyral; 05212009 at 09:19 AM.

You've a syntax error thereand you're making things more difficult than you need.
Code:
Number.prototype.isPrime = function () {
var n = Math.abs (this);
for (var i = 2; i < n; i++) if (n % i == 0) return false;
return true;
}
n = Number (prompt ('Number', ''));
alert (n.isPrime() ? 'Prime' : 'Not prime');
“The power of the Web is in its universality. Access by everyone regardless of disability is an essential aspect.”
—Tim BernersLee, W3C Director and inventor of the World Wide Web

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):
Code:
Number.prototype.isPrime = function ()
{
var
n = Math.abs(this), m = Math.sqrt(n), i = 1;
while (++i <= m)
{
if (!(n % i))
{
return false;
}
}
return true;
}
n = Number (prompt ('Number', ''));
alert (n.isPrime() ? 'Prime' : 'Not prime');

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.
Code:
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.

Watch out the typo! :
Code:
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;
}
Last edited by Kor; 01132010 at 07:44 AM.

Code:
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.

Why do you do an or with two identical conditionals?

What is with my typos in this thread!
Code:
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%(i1) == 0) {
return false;
}
}
return true;
}

Something's not right with Declan's code
it returns true for the following nonprime 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 :
Code:
Number.prototype.isPrime= function(){
if(this== 2) return true;
var n= Math.floor(this);
if(n!= this  this< 3  !(this%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 nonintegers.
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 nonnegative integers {0, 1, 2, ...}
Last edited by mrhoo; 01132010 at 12:47 PM.

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.
Code:
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 = n1;
for (let i = 0; p[i]< s; i++) {
if (t%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;
}
}
}

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 miscalled those 20 odd.
Last edited by mrhoo; 01132010 at 06:01 PM.

I figured it out. The problem was square numbers (in particular (6n1)^2). Take 25. The squareroot 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 .
Code:
function isPrime(n) {
n = Math.abs(n);
if (n == 2  n == 3) return true;
if (n%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.
Last edited by Declan1991; 01142010 at 12:15 PM.

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.

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

Here's a development (written by rnd me), following your idea:
Number.prototype.isPrime
Code:
(function(){function isPrime(){ var n=this;
if(isPrime[n]){ return true; }
if( n<11 ! ((n%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;
}());
Thread Information
Users Browsing this Thread
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

