www.webdeveloper.com
Results 1 to 15 of 15

Thread: Is Prime Help

  1. #1
    Join Date
    May 2009
    Posts
    9

    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 &#37; i == 0) {
    return true;
    break;

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

    }
    </script>
    Last edited by Jaxyral; 05-21-2009 at 09:19 AM.

  2. #2
    Join Date
    Nov 2002
    Location
    Baltimore, Maryland
    Posts
    12,270
    You've a syntax error there--and 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 &#37; 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 Berners-Lee, W3C Director and inventor of the World Wide Web

  3. #3
    Join Date
    May 2009
    Posts
    150
    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 &#37; i))
    		{
    			return false;
    		}
    	}
    	return true; 
    }
    
    n = Number (prompt ('Number', ''));
    alert (n.isPrime() ? 'Prime' : 'Not prime');

  4. #4
    Join Date
    Aug 2007
    Posts
    3,767
    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&#37;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.
    Great wit and madness are near allied, and fine a line their bounds divide.

  5. #5
    Join Date
    Dec 2003
    Location
    Bucharest, ROMANIA
    Posts
    15,428
    Watch out the typo! :
    Code:
    function isPrime(n) {
        n = Math.abs(n);
        var l = Math.sqrt(n);
        if (n&#37;2) return false;
        for (i = 3; i < m; i += 2) {
            if (!(n % i)) {
                return false;
    	}
        }
        return true; 
    }
    Last edited by Kor; 01-13-2010 at 07:44 AM.

  6. #6
    Join Date
    Aug 2007
    Posts
    3,767
    Code:
    function primes(n) {
    	n = Math.abs(n);
    	if (n&#37;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.
    Great wit and madness are near allied, and fine a line their bounds divide.

  7. #7
    Join Date
    May 2009
    Posts
    150
    Why do you do an or with two identical conditionals?

  8. #8
    Join Date
    Aug 2007
    Posts
    3,767
    What is with my typos in this thread!
    Code:
    function primes(n) {
    	n = Math.abs(n);
    	if (n&#37;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;
    }
    Great wit and madness are near allied, and fine a line their bounds divide.

  9. #9
    Join Date
    Feb 2006
    Posts
    2,926
    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 :

    Code:
    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, ...}
    Last edited by mrhoo; 01-13-2010 at 12:47 PM.

  10. #10
    Join Date
    Aug 2007
    Posts
    3,767
    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 = 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;
    		}
    	}
    }
    Great wit and madness are near allied, and fine a line their bounds divide.

  11. #11
    Join Date
    Feb 2006
    Posts
    2,926
    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.
    Last edited by mrhoo; 01-13-2010 at 06:01 PM.

  12. #12
    Join Date
    Aug 2007
    Posts
    3,767
    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 .
    Code:
    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.
    Last edited by Declan1991; 01-14-2010 at 12:15 PM.
    Great wit and madness are near allied, and fine a line their bounds divide.

  13. #13
    Join Date
    Feb 2006
    Posts
    2,926
    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.

  14. #14
    Join Date
    Aug 2007
    Posts
    3,767
    I was getting worried, I'd posted three functions in this thread, and none worked!
    Great wit and madness are near allied, and fine a line their bounds divide.

  15. #15
    Join Date
    Dec 2003
    Location
    Bucharest, ROMANIA
    Posts
    15,428
    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&#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;
    }());

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
  •  
HTML5 Development Center



Recent Articles