Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: Finding prime numbers code issue

1. Here's (nearly) the best I can do with the Sieve of Erastothenes:
Code:
```<script type="text/javascript">
var nums = [ ];
var primes = [2];
var MAXNUM = 500; // change this as desired

// run the actual seive
for ( var chk = 3; chk < MAXNUM; chk += 2 )
{
if ( nums[chk] == null )
{
primes.push(chk);
for ( var mark = chk*3; mark < MAXNUM; mark += chk*2 )
{
nums[mark] = 0; // any non-null would do
}
}
}
</script>```
Improvements:
(a) no need to initialize the array
(b) only checks odd numbers
(c) only marks odd increments of a found prime
(d) doesn't bother marking a found prime

The next step: Would only save memory, not speed. And probably not even that with JavaScript coding. Have each element of the array represent an ODD number. That is, the element numbering doesn't match the numbers represented. So the array can be half the size it is now.

Aside from changing algorithms, do you see a way to improve that?

2. Let's say that you want to check the first million primes, notice that I've conveniently chosen a limit that is the square of another number, and that number is composite ! Then you only need to check against primes that are less than 1,000. Make your life simpler by setting reasonable conditions.

3. DrDos: Ummm...no.
(a) The first million *PRIMES* will not be found in the first million numbers. Not even close. I think you mean "all prime numbers that are less than one million".
(b) If that's a comment on my Sieve of Erastothenes implementation, I still don't see it. With the Sieve, any non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked numbers so won't find all the primes.

4. Originally Posted by Old Pedant
DrDos: Ummm...no.
(a) The first million *PRIMES* will not be found in the first million numbers. Not even close. I think you mean "all prime numbers that are less than one million".
(b) If that's a comment on my Sieve of Erastothenes implementation, I still don't see it. With the Sieve, any non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked numbers so won't find all the primes.
You're right sir! I really meant the primes in the first million numbers, not the first million primes.

5. Okay, I do see that the marking and checking can be done separately, and then the marking only has to go to the square root of the max:
Code:
```<script type="text/javascript">
var nums = [ ];
var primes = [2];
var MAXNUM = 500; // change this as desired

// run the actual seive
for ( var chk = 3; chk < Math.sqrt(MAXNUM); chk += 2 )
{
if ( nums[chk] == null )
{
for ( var mark = chk*3; mark < MAXNUM; mark += chk*2 )
{
nums[mark] = 0; // any non-null would do
}
}
}
for ( var chk = 3; chk < MAXNUM; chk += 2 )
{
if ( nums[chk] == null ) primes.push(chk);
}
</script>```
All that really saves is the time for the inner for loop to discover that it won't run at all once chk is past the square root of max. At the expense of having to run another loop to collect the primes. I'd guess that's close to a wash.

6. Originally Posted by Old Pedant
Okay, I give up. How does using the square root of the number being checked apply to the Sieve of Erastothenes algorithm???
Yeah, you're right – I mixed some things up there (namely the sieve and a prime number check). My mistake.

7. A simple page for prime numbers which use the preceding primes to test a new number.

And a more subtle function (from rnd.me ? I can not find the post) that stores the previous calculations to go faster
Code:
```<script type="text/javascript">
(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;
}());
// Use
var nmb=33353;
</script>```
After 9 you have only to check 5+6*k and 5+6*k+2 (the other are even or divisible by 3)
Strange prime numbers : 11113, 11117, 11119, 22229, 33331, 44449, 77773, 88883, 99991 ...

8. Code:
```Is this number prime? <input type = "text" id = "pn" onblur = "return alert(Number.prototype.isPrime(this.value))">

<script type = "text/javascript">

Number.prototype.isPrime = function (which) {
var num = Number(which), counter;
if (num === 2) {
return true;
}
if (num < 2 || (num / 2) === Math.floor(num / 2) || num !== Math.floor(num)) {
return false;
}
else {
for (counter = 3; counter <= Math.sqrt(num); counter += 2) {
if (num % counter === 0) {
return false;
}
}
return true;
}
}

</script>```

Page 2 of 2 First 12