PDA

View Full Version : Find Prime Numbers - Need Assistance



pzamory
Feb 4th, 2011, 11:51 PM
I would like to create a script that allows for a user to input two integers and to have the script show all the prime numbers that fall between them.

Any thoughts?

Thanks

Philip M
Feb 5th, 2011, 09:52 AM
Is this homework or a student assignment? If it is not homework that is easily done. If it is homework, see forum Rule 1.5.

"In the beginner's mind there are many possibilities, but in the expert's mind there are few” - Shunryu Suzuki (Japanese Zen priest, ?-1971)

oVTech
Feb 5th, 2011, 03:10 PM
Is this homework or a student assignment? If it is not homework that is easily done. If it is homework, see forum Rule 1.5.

"In the beginner's mind there are many possibilities, but in the expert's mind there are few” - Shunryu Suzuki (Japanese Zen priest, ?-1971)


Do you mind sharing the code anyway, I'm just curious! I actually have a script that does what he asked for, but it's kinda long and problematic. Since you said that is easily done I am assuming it must be shorter and cleaner. Peace.

mrhoo
Feb 5th, 2011, 03:58 PM
Finding prime numbers with javascript involves two special features-

First, there is an upper limit of integer accuracy, about 10 to the 15th,
beyond which you need a BigInt math to find any primes.

And second, even in the supported range, high primes can take long enough to calculate to freeze a browser,
so you need to break up the calculation with time outs or web workers. Beyond 10 to the 20th or so,
however, you start needing to work with 'probable' primes, or use a more mathematical language...

There are some very good sites that are devoted to primes and calculating them- here is one, with links to others:

http://primes.utm.edu/

venegal
Feb 5th, 2011, 04:10 PM
Do you mind sharing the code anyway, I'm just curious! I actually have a script that does what he asked for, but it's kinda long and problematic. Since you said that is easily done I am assuming it must be shorter and cleaner. Peace.

Would you mind posting the long and problematic script? I'd like to see what it does.

I'd probably write it something like this, implementing the Sieve of Eratosthenes:

var start = 1000;
var end = 2000;

var i, j, numbers = [];
var endSqrt = Math.sqrt(end);
for (i = 2; i <= end; numbers[i] = i++) {};

for (i = 2; i < endSqrt; i++) {
if ( ! numbers[i]) continue;
for (j = 2 * i; j <= end; j += i) {
delete numbers[j];
}
}

alert(numbers.splice(start).filter(function (value) {return value;}).join(', '));

Of course that's only feasible for small enough numbers, but that's probably what this is about anyway.

I didn't do the user input part, of course, and used JS1.6 code in the output, which is incompatible to IE, so the OP can't just copypaste this for homework.

Philip M
Feb 5th, 2011, 04:39 PM
This is what I had in mind:-


<html>
<head>

<script type = "text/javascript">

Number.prototype.primeFactors= function(){
var n = this, f= [], next = 2;
while (next*next <= n) {
if (n%next == 0){
f.push(next);
n = n/next;
}
else {next++}
}
if(n!=1) {f.push(n)}
return f;
}

function genprimes() {
var lowest = parseInt(document.getElementById("low").value);
var highest = parseInt(document.getElementById("high").value);
if (isNaN(lowest) || isNaN(highest)) {
alert ("You must enter numbers in both boxes!");
document.getElementById("low").value = "";
document.getElementById("high").value = "";
return false;
}
if ((lowest > highest) || (lowest <0) || (highest <0)) {
alert ("Invalid Numbers - Highest must be >= Lowest");
document.getElementById("low").value = "";
document.getElementById("high").value = "";
return false;
}

document.write ("<h3>Primes between " + lowest + " and " + highest + ":</h3> \n");

var count = 0;
for (var n = lowest; n<=highest; n++) {
var f = n.primeFactors();
if (f == n) {
document.write(n + " ");
if (++count % 10 == 0) {document.write ("<br>")}

}
if (count >999) { // stop at 1000!
n = 9e15;
}
}

document.write ("<h4>Total count: " + count + "</h4>");

}
</script>
</head>
<body>

Lowest Number In Range <input type = "text" id = "low" size = "7" maxlength = "7">
<br>
Highest Number In Range <input type = "text" id = "high" size = "7" maxlength = "7">
<br><br>
<input type = "button" value = "Generate prime numbers within the range" onclick = "genprimes()">
</body>
</html>

Obviously that cannot be passed off as the OP's own work! In fact I think it originates with mrhoo. There are of course simpler (and less efficient) solutions.

I have built in a restriction to 7-digit numbers, which is probably adequate for most purposes. As mrhoo says, high primes can take long enough to calculate to freeze a browser,

venegal
Feb 5th, 2011, 05:32 PM
Obviously that cannot be passed off as the OP's own work! In fact I think it originates with mrhoo. There are of course simpler (and less efficient) solutions.


Simpler solutions, sure. You'd be hard pressed to find any less efficient solutions though this script is very badly done:

I just benchmarked it for generating all primes up to 100000 (and I removed the output, so no time is lost rendering). The one you posted took about 1000ms, while mine took about 50ms (and that ratio figues to get much worse for higher numbers).

It's very obvious, too, why it's so slow: It does a full prime factorization on all the numbers, which is completely unnecessary.

So, all in all, it's clunky, and it's slow, so there's really no reason to use it.

pzamory
Feb 5th, 2011, 06:03 PM
Actually I wish. I have been out of college for 35 years now.... Perhaps I should go back.

Punch cards were in vogue when I was in school. We have come a long way.

oVTech
Feb 5th, 2011, 06:17 PM
Yeah, very nice to see what you guys did with yours. Here is what I got so far. Perhaps it's not as long as I thought after I cut some unnecessary code. Really though, the math part of it throws me off a little. venegal would you mind commenting yours a little, because I am not sure what's going on with the numbers there (although the Sieve of Eratosthenes makes sense to me on a piece of paper, when inside a script, it's kinda confusing). Nice little script though! Philip M I will definitely play around with yours too.



/*
* Submitted by UMBRO on "kerneltrap.org" in 2006 & edited by oVTech in 2010
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
*/
function getPrimes (theNumbers) {
var sqrtNums = Math.floor( Math.sqrt( theNumbers ) );
var output = document.getElementById('outputNums');
var isPrime = true;
for (var c=2; c<=sqrtNums; c++) {
if ( (theNumbers%c) == 0) {
isPrime = false;
break;
}
}
if (isPrime == true) {
output.style.display = "block";
output.innerHTML += theNumbers + ": is a prime. <br \/>"
}
}
function initPrimeSearch () {
var f = document.forms["primesForm"];
var startNumber = parseInt( f.num1.value );
var endNumber = parseInt( f.num2.value );
if ( (isNaN(startNumber) || isNaN(endNumber)) || (startNumber >= endNumber || (f.num1.value <=0 || f.num2.value <=0)) ) {
alert("Only numbers are allowed! &\nThe 1st number has to be smaller than the 2nd number! &\nThe numbers have to be non-negative and non-zero numbers!");
}
else {
for (var j=startNumber; j<=endNumber; j++) {
if ( (j<=3) ) {//Although 1 isn't a prime, it is included
//console.log(j + ": is a prime.");
}
else {
getPrimes(j);
}
}
}
}
window.onload = function () {
var output = document.getElementById('outputNums');
output.style.display = "none";
var btn = document.getElementById('primeBtn');
btn.onclick = initPrimeSearch;
}


/*- - - - - - - - HTML - - - - - - - - */
<form name="primesForm" action="">
Enter 1st Number:<br />
<input type="text" name="num1" value="4" /> <br /> <br />

Enter 2nd Number: <br />
<input type="text" name="num2" value="168" /> <br /> <br /> <br />

<input type="button" value="Get Prime Numbers" id="primeBtn" />
</form>

<div id="outputNums">
</div>



PS: No reason of arguing here about whose script is better though and how many milliseconds it takes, we have years in front of us to worry about, not a 1000s! :) People approach things differently, our minds aren't the same. Peace!

Philip M
Feb 5th, 2011, 06:18 PM
So, all in all, it's clunky, and it's slow, so there's really no reason to use it.

OK, try this instead (I suspect even slower!). But 1000ms = 1 second to generate all primes up to 100000 - obviously 50ms is much faster, but in reality can anyone tell the difference? And both scripts require additional (the same) time for rendering.



<html>
<head>

<script type = "text/javascript">

function genprimes () {
var lowest = Math.abs(parseInt(document.primes.low.value));
var highest = Math.abs(parseInt(document.primes.high.value));
if (isNaN(lowest) || isNaN(highest)) {
alert ("Please specify two (positive) integer numbers.");
document.primes.low.value = "";
document.primes.high.value = "";
return false;
}
else {
if (lowest > highest) { // switch if highest < lowest
var temp = lowest;
lowest = highest;
highest = temp;
}
}

document.write ("<h3>Primes between " + lowest + " and " + highest + ":</h3> \n");

var count = 0;
for (var i=Math.max(2,lowest); i<=highest; i++) {
if (isPrime (i)) {
document.write (i + " ");
if (++count % 10 == 0) {document.write ("<br>")}
}
}
document.write ("<h4>Total count: " + count + "</h4>");
}

function isPrime (i) {
for (var j=2; j<=Math.sqrt(i); j++) {
if (i % j == 0) {return false}
}
return true;
}

</script>
</head>

<body>

<form name="primes">
Lowest Number In Range <input type = "text" id = "low" size = "6" maxlength = "6">
<br>
Highest Number In Range <input type = "text" id = "high" size = "6" maxlength = "6">
<br><br>
<input type = "button" value = "Generate prime numbers within the range" onclick = "genprimes()">
</form>

</body>
</html>

mrhoo
Feb 5th, 2011, 07:06 PM
// Finding primes often goes with factoring numbers
// The speed of the calculations is less important than
// making sure an answer is arrived at without browser freeze.

<!doctype html>
<html lang= "en">
<head>
<meta charset= "utf-8">
<title>Limited Factoring in Script</title>
<style media= "screen">
html{
overflow-y:scroll;
}
body{
margin: 1em;
}
input, span, label, textarea, button, select{
color: black;
font-size: 1em;
font-weight: 600;
margin: 2px;
}
input, select{
text-align:right;
background-color:white;
}
p{
font-size: 1em;
margin:1em 1ex;
}
button, select{
font-family:sans-serif;
cursor: pointer;
}
button:hover, button:focus{
color: red;
}
button[disabled],select[disabled]{
color: black;
cursor: default;
}

#primefactDiv{
font-size:1.2em;
background-color:white;
color:black;
position:relative;
}
#stepIn{
margin-left: 1em;
color:red;
border: none;
opacity:1.0;
background-color:white;
}
input{border:1px black ridge;border-width:2px 2px 1px 2px}
#highprimesTa{
border:none;
}
#outputMsg{
font-size:1.1em;
}

#primesetTo,#stepIn{
text-align: left;
}
#primeset_p{
width: 96%;
margin:auto;
font-family:"Courier New",courier,monospace;
font-weight:500;
}
#workingMsg,#supspan{
color: green;
font-size: 1.2em;
visibility: hidden
}
#nth_p{
visibility:hidden
}
#detailsMsg{
margin-left:1em;
color:green;
}

</style>
<style>
@media screen and (min-width:900px) {
#primefactDiv{
font-size:1.2em;
}
p{max-width:800px}
#setsDiv1, #setsDiv2{
width:48%;
min-width:380px;
float:left;
}
#setsDiv1{
padding-right:1em;
}
#setsDiv2{
padding-left:1em;
}

}
@media screen and (max-width:800px){
#primefactDiv{
font-size:1em;
}
#setsDiv1, #setsDiv2{
width:auto;
}
}
</style>
<script>
var Run= window.Run || {};

function Mr(hoo){
if(!hoo) return null;
if(hoo===window || hoo===document)return hoo;
if(typeof hoo== 'string'){
return document.getElementById(hoo)|| null;
}
if(hoo.nodeType== 1) return hoo;
return null;
}

navigator.sayswho= (function(){
var N= navigator.appName, ua= navigator.userAgent, tem, ie;
var M= ua.match(/(opera|chrome|safari|firefox|msie)\/?\s*(\.?\d+(\.\d+)*)/i);
if(M && (tem= ua.match(/version\/([\.\d]+)/i))!= null) M[2]= tem[1];
M= M? [M[1], M[2]]: [N, navigator.appVersion,'-?'];
return M;
})();

Array.prototype.indexOf= Array.prototype.indexOf || function(what, i){
i= i || 0;
var L= this.length;
while(i< L){
if(this[i]=== what) return i;
++i;
}
return -1;
}
Array.prototype.omega= function(val){
var i= this.length? this.length-1: 0;
if(val) this[i]= val;
return this[i];
}

var Rp={
clear:function(){
var a= arguments, L= a.length, hoo;
while(L>0){
hoo= Mr(a[--L]);
if(hoo){
if(hoo.tagName=='INPUT'){
hoo.value='';
if(hoo.checked)hoo.checked=false;
}
else Run.saywhat(hoo,' ');
}
}
},
lockInput: function(boo){
var a= arguments, L= a.length, hoo;
boo= !!boo? 'readOnly': false;
while(L> 1){
if((hoo= Mr(a[--L]))!= null) hoo.readOnly= boo;
}
},
onOffBtn: function(boo){
var a= arguments, L= a.length, hoo;
boo= !!boo? false: 'disabled';
while(L> 1){
if((hoo= Mr(a[--L]))!= null) hoo.disabled= boo;
}
},
saywhat: function(who, text, append){
who= Mr(who);
if(!who) return '';
if(append!== true && text!= undefined){
while(who.firstChild){
who.removeChild(who.lastChild);
}
}
if(text){
who.appendChild(document.createTextNode(text));
}
text= who.textContent || who.innerText;
who= null;
return text || '';
}
}
for(var p in Rp){
Run[p]= Rp[p];
}
if(window.addEventListener){
Run.handler= function(who, what, fun, mod){
mod= !!mod;
who= Mr(who);
if(who){
who.addEventListener(what, fun, mod);
}
}
Run.unhand= function(who, what, fun ,mod){
mod=!!mod;
who=Mr(who);
if(who){
who.removeEventListener(what, fun, false);
}
}
}
else{
Run.handler= function(who, what, fun){
who= Mr(who);
if(who){
who.detachEvent('on'+what, fun);
who.attachEvent('on'+what, fun);
}
}
Run.unhand= function(who, what, fun){
who=Mr(who);
if(who){
who.detachEvent('on'+what, fun);
}
}
}
</script>
<script>
//prime number and factor calculation and display
var Pf={
beginwork: function(){
Mr('workingMsg').style.cssText='visibility:visible';
Run.onOffBtn(true,'quitBtn');
Run.clear('detailsMsg','stepIn');
Mr('numberIn').focus();
Run.onOffBtn(false,'factorBtn','primesetBtn','collectBtn','nthBtn',
'primesetSel','randnumBtn');
Run.lockInput(true,'primesetFrom','primesetTo','numberIn','nthPrimeIn');
Pf.clock=new Date();
},
collect: function(v){
var obj, ax, pstep= Pf.step2 || Pf.step, n= 3, p= Pf.sieve;
if(!v) return Pf.reset();
if(!Pf.show){
Pf.beginwork();
Mr('numberIn').focus();
Run.clear('outputMsg');
}
if(p){
pstep= Pf.makeSieve.steps;
ax= Pf.previous(v);
if(ax) return Pf.reset();
else n= p.omega()+2;
}
else Pf.sieve= [2];
obj={
num: n, top: v, steps: pstep
}
for(var p in obj) Pf.makeSieve[p]= obj[p];
Pf.tick= setTimeout(function(){
Pf.clock= new Date();
Pf.makeSieve();
},0);
},
elapsed:function(){
var t='';
if(Pf.clock){
t=new Date()-Pf.clock;
t= (t/1000).toFixed(3)+' seconds';
}
return t;
},
exponents: function(f){
var a= [], tem, i, str= '';
while(f.length){
tem= f.shift();
i= a.push([tem, 1])-1;
while(f[0]=== tem){
a[i][1]= a[i][1]+1;
f.shift();
}
if(a[i][1]> 1) a[i]= ' '+a[i][0]+'<sup>'+a[i][1]+'</sup> ';
else a[i]= a[i][0];
}
return a.join('*');
},
factoring:function(F){
var n= F.num, limit=F.limit, count= F.count,
fs= F.factors, p= Pf.sieve, L=p.length,i=F.itm,
next= p[i];

while(next<=limit && count> 0){
if(n%next== 0){
fs.push(next);
if(F.square)fs.push(next);
n= n/next;
limit=Math.sqrt(n);
}
else next= p[++i] || next+2;
--count;
}
if(fs.length== 0 && next<=limit){
Mr('stepIn').value= next;
F.next= next;
F.num= n;
F.limit=limit;
if(i<L){
F.itm=i;
Pf.tick= setTimeout(function(){Pf.factoring(F)}, 0);
}
else{
Pf.tick= setTimeout(function(){Pf.factorize(F)}, 0);
}
return;
}
else{
if(n!= 1) fs.push(n);
return Pf.factorShow(F);
}
},
factorize: function(F){
var fs= F.factors, n= F.num, next= F.next,
limit= F.limit, count= F.count, t, timer= new Date();
Mr('stepIn').value= next;
if(Pf.wait) return Pf.reset();
while(next<=limit && count> 0){
if(n%next== 0){
fs.push(next);
if(F.square)fs.push(next);
F.num= n= n/next;
limit=Math.sqrt(limit);
}
else next= next+2;
--count;
}
t= new Date()-timer;
if(next<limit){
F.next= next;
F.limit=limit;
F.num=n;
if(t<50) F.count*= 2;
else if(t> 200) F.count/= 2;
Pf.tick= setTimeout(function(){Pf.factorize(F)}, 0);
}
else{
if(n!= 1) fs.push(n);
Pf.factorShow(F);
}
},
factorShow: function(F){
var t=Pf.elapsed(),fs=F.factors, f1= F.val, s='',i, pp=Pf.proven;
if(F.square && fs.length==1){
fs.push(fs[0]);
}
if(fs.length== 1){
i=f1<Pf.lastN ? Pf.sieve.indexOf(f1):-1;
if(i!=-1)s= ' #'+(i+1);
else if(pp.indexOf(f1)==-1)pp.push(f1);
Run.saywhat('outputMsg', f1+' is prime'+s);
}
else{
s=(F.square && fs.length>2)? '[ '+Math.sqrt(f1)+'<sup>2</sup> ]; ':'';
Mr('outputMsg').innerHTML= s+' Prime factors of '+f1+'= '+Pf.exponents(fs);
}
if(Mr('detailsCheck').checked){
Run.saywhat('detailsMsg',F.count+' rpm in '+t);
}
Mr('stepIn').value= '';
Pf.reset();
},
factory: function(){
var n= Pf.validInt();
if(!n) return;
var i, ax= Math.sqrt(n);
Pf.beginwork();
Run.clear('outputMsg');
Mr('numberIn').focus();
var facts={
num: n, val:n, factors: [], itm: 0,
limit:ax, count:Pf.step2,next:2, square:false
}
if(Pf.lastN>n && Pf.sieve.indexOf(n)!= -1){
facts.factors[0]=n;
return Pf.factorShow(facts);
}
else if(Pf.proven.indexOf(n)!=-1){
facts.factors[0]=n;
return Pf.factorShow(facts);
}
else if(ax%1===0 && ax*ax===n){
facts.square=true;
facts.num=ax;
facts.limit=Math.sqrt(ax);
}
Pf.tick= setTimeout(function(){
Pf.factoring(facts)
}, 0);
},
makeSieve: function(obj){
var F= Pf.makeSieve;
var limit, div, isPrime, S= Pf.sieve,L=S.length,
t= F.top, n= F.num, count= F.steps, timer= new Date();

while(n <= t && count> 0 && !Pf.wait){
div= 3;
limit= Math.sqrt(n);
isPrime= true;
while(div<=limit){
if(n%div=== 0){
isPrime= false;
break;
}
div+= 2;
}
if(isPrime){
S[L++]= n;
}
n+= 2;

--count;
}
if(n> t) Pf.report();
else{
F.num= n;
timer= new Date()-timer;
Mr('nthPrimeIn').value=L;
if(timer<50) F.steps*= 2;
else if(timer> 200) F.steps/= 2;
if(Pf.wait) return Pf.report();
else Pf.tick= setTimeout(F,0);
}
},
getRange:function(n){
if(typeof n !='number') n= Pf.lastN+Pf.vee;
Mr('primesetTo').value=n;
Mr('primesetFrom').value=(n-1000);
Run.clear('outputMsg');
Mr('nthPrimeIn').focus();

var n=Pf.validInt('primesetTo');
if(n && n>Pf.lastN){
Run.clear('primeset_p');
Pf.collect(n);
}
else Pf.reset();
},
getSet:function(){
var i=Mr('primesetSel').selectedIndex,n1,n2;
if(i==0) return;
if(i==1){
n1=2;
n2=10;
}
else{
n1=Math.pow(10,i-1);
n2=Math.pow(10,i);
}
Mr('primesetFrom').value=n1;
Mr('primesetTo').value=n2;
return Pf.showSet();
},
hiPrimes:[],
init: function(){
delete Pf.details;
Pf.step2=Pf.makeSieve.steps;
Mr('numberIn').value= '9007199254740991';

if(!Pf.wait) Run.clear('outputMsg','stepIn');
Run.handler('primefactDiv','click',Pf.operator);
Run.handler('primesetSel','change',Pf.getSet);
Run.handler('quitBtn','click',Pf.quit);

return Pf.reset();
},
lastN: 2,
nthPrime:function(){
var n= +(Mr('nthPrimeIn').value);
Mr('nthPrimeIn').focus();
if(isNaN(n)){
n=Pf.sieve.length;
Mr('nthPrimeIn').value=n;
}
np=Pf.sieve[n-1];
if(typeof np=='number'){
Run.saywhat('nth_span','prime #'+n+' is '+np);
}
else{
Mr('nthPrimeIn').value= Pf.sieve.length;
Run.saywhat('nth_span','You can collect more prime #s');
Mr('collectBtn').focus();
}
Pf.reset();
},
operator:function(e){
e=e || window.event;
var who=e.target || e.srcElement, hoo= who.id;
if(who.nodeName=='BUTTON' && !Pf.wait){
switch(hoo){
case 'factorBtn':return Pf.factory(e);
case 'primesetBtn': return Pf.showSet();

case 'collectBtn': return Pf.getRange();
case 'nthBtn': return Pf.nthPrime();
case 'randnumBtn': return Pf.randomFactor();
default: return true;
}
}
return true;
},
previous: function(n){
var tem, p= Pf.sieve, ax,
lp= p.omega();
if((ax= p.indexOf(n))!= -1) return [ax+1, n];
if(n> lp){
if(n<= Pf.lastN) return [p.length, lp];
return null;
}
while((ax= p.indexOf(n))== -1)--n;
return [ax+1, p[ax]];
},
primeTest: function(F){
var p= Pf.hiPrimes, n= F.num, next= F.next, t, timer= new Date(),
count= F.count, size= F.size;
while(n> 2 && next*next<=n && count> 0){
if(n%next=== 0){
n-= 2;
next= 3;
//--count;
}
else next+=2;
--count;
}
t= new Date()-timer;
if(Pf.wait || n<3){
clearTimeout(Pf.tick);
if(n<3) p.push(2);
return Pf.showHi(F);
}
else if(count<= 0 && next*next<=n){
if(t<50) F.count*= 2;
else if(t> 200) F.count/= 2;
F.next= next;
F.num= n;
Pf.tick= setTimeout(function(){
Mr('stepIn').value=next;
Pf.primeTest(F)
},
0);
}
else{
if(n!= 1) p.push(n);
F.next= 3;
F.num= n- 2;

if(--size==0 || Pf.wait) Pf.showHi(F);
else Pf.tick= setTimeout(function(){
F.timer=Pf.elapsed();

Pf.primeTest(F)
},
0);
}
},

proven:[],
quit: function(){
clearTimeout(Pf.tick);
Pf.wait= true;
Mr('stepIn').value='Operation halted - '+Pf.elapsed();
if(!Pf.hiPrimes.length)return Pf.report();
return Pf.reset();
},
randomFactor:function(){
var flip=Math.random()>.25,
range=flip? 9007199254740989 :2000,
n=Math.floor(Math.random()*range)+2;
if(flip && n%2===0)--n;
Mr('numberIn').value= n;
return Pf.factory();
},
report: function(t){
clearTimeout(Pf.tick);
var t= Pf.elapsed(), x=Pf.sieve.omega(), f1,
last= Pf.wait? Pf.makeSieve.num: Pf.makeSieve.top;
if(last> Pf.lastN) Pf.lastN= last;
var str, F= Pf.makeSieve, pset= Pf.sieve, steps= F.steps,
det=Pf.details!==undefined || Mr('detailsCheck').checked;
Mr('nthPrimeIn').value=Pf.sieve.length;
if(det || Pf.wait){
if(!Pf.wait) Run.saywhat('detailsMsg',t+' at '+steps+' rpm');
if(Pf.details=== 0) return Pf.init();
}
if(/#/.test(Run.saywhat('nth_span')))return Pf.nthPrime();
if(!Pf.wait)Run.clear('stepIn');
if(Pf.show) return Pf.showSet();

Pf.reset();
},
reset: function(){
Run.onOffBtn(false,'quitBtn');
Run.onOffBtn(true,'primesetBtn','factorBtn','bigPrimeBtn','collectBtn',
'nthBtn','primesetSel','randnumBtn');
Run.lockInput(false,'primesetFrom','primesetTo','numberIn','nthPrimeIn');

Mr('primesetSel').selectedIndex=0;
delete Pf.wait;
delete Pf.show;
delete Pf.clock;
delete Pf.tick;
Pf.hiPrimes.length=0;
Pf.tick=setTimeout(function(){
Mr('workingMsg').style.cssText= '';
},0);
Pf.proven.sort(function(a,b){
return a-b;
});
return true;
},

showSet: function(){
if(!Pf.show) Pf.beginwork();
var who= Mr('primeset_p');
Run.saywhat(who,' ');
var ax1, ax2,itm,str= '', from= Pf.validInt('primesetFrom'),
to= Pf.validInt('primesetTo'), p= Pf.sieve;
if(!from || !to || from> to) return Pf.reset();
if(to> Pf.lastN){
Pf.show= true;
Pf.tick=setTimeout(function(){
Pf.getRange(to);
}, 0);
return;
}
if(to-from>10000){
if(!confirm('That\'s a lot of primes to look \nare you sure?')){
itm=Mr('primesetTo').value;
Mr('primesetFrom').value=itm-1000;
Mr('primesetTo').focus();
return Pf.reset();
}
}
while((ax1= p.indexOf(from))== -1)++from;
while((ax2= p.indexOf(to))== -1)--to;
p= p.slice(ax1, ax2+1);
Run.saywhat(who, p.length +' primes between '+
Mr('primesetFrom').value+' and '+Mr('primesetTo').value);
who.appendChild(document.createElement('br'));

Pf.tick=setTimeout(function(){
Pf.showWhat(p);
},0);
},
showWhat: function(p){
var who= Mr('primeset_p'), str= p.shift() || '', str2;
who.appendChild(document.createTextNode(str+' '));
if(p.length && !Pf.wait){
Pf.tick=setTimeout(function(){
Mr('stepIn').value= str;
Pf.showWhat(p)
},
0);
}
else{
Mr('stepIn').value= '';
if(Pf.wait){
str2= 'Operation halted at '+str;
who.replaceChild(document.createTextNode(str2), who.firstChild);
}
Pf.reset();
}
},
update: function(L, timer){
Mr('nthPrimeIn').value=L;
if(timer<50) Pf.makeSieve.steps*= 2;
else if(timer> 200) Pf.makeSieve.steps/= 2;
if(Pf.makeSieve.steps<=8)Pf.quit();
},
validInt: function(who){
who= Mr(who) || Mr('numberIn');
var limit=9007199254740991, v= parseInt(who.value),
str='Input an integer between 2 and '+ limit;
if(isNaN(v) || v<2 || v> limit){
if(!isNaN(v) && v>limit)str=str.replace('between 2 and','less than');
Mr('stepIn').value=str ;
who.value= '';
who.focus();
return false;
}
who.value=v;
return v;
}
}
Run.handler(window,'unload', function(){
clearTimeout(Pf.tick);
Run.clear('outputMsg','detailsMsg','nth_span','stepIn');
Run.unhand('primefactDiv','click',Pf.operator);
Run.unhand('primesetSel','change',Pf.getSet);
Run.unhand('quitBtn','click',Pf.quit);


for(var p in Pf) delete Pf[p];
return true;
});
Run.handler(window,'load',function(){
Pf.step= 65536;
Pf.vee= 1000000;
/*@cc_on
@if(@_jscript_version> 5.5){
Pf.step= 32768;
Pf.vee= 200000;
Pf.IE=true;
}
@else{
return;
}
@end
@*/
Mr('stepIn').value= '';
Mr('primesetFrom').value= '100';
Mr('primesetTo').value= '1000';
if(Pf.IE){
Run.saywhat('browserid',navigator.sayswho.join(' ')+
' is some slower at these calculations than other browsers, but it\'ll get there, in time...')
}
else{
Run.saywhat('browserid',navigator.sayswho.join(' '));
}
Mr('primesetSel').selectedIndex=0;
Pf.details= 0;
Pf.collect(Pf.vee);
});
</script>

</head>
<body>
<h1>The limits of javascript- factoring numbers below 2<sup>53</sup>-1</h1>
<a href="www.yankeeweb.com/webshop.html">by Kenneth Tibbetts</a>
<h2 id= "browserid"> &nbsp;</h2>
<div id="primefactDiv">

<p>
Any integer between 2 and 9007199254740991 can be factored, or proven prime, with native javascript.
The time it takes to do so will depend on the size of its factors and the speed of your computer</p>
<p>
<input id= "numberIn" size= "20" value= "">
<button id= "factorBtn">Factors</button><button id= "randnumBtn" title="Factor a random integer">Random</button>

<button id= "quitBtn"> Quit</button><span id= "workingMsg"> Working...</span></p>
<p>
<span style="visibility:hidden">2<sup>2</sup></span><span id="outputMsg">&nbsp;</span></p>
<p>
<label for= "detailsCheck"> details </label> <input id= "detailsCheck" checked="checked" type= "checkbox">
<span id="detailsMsg">&nbsp;</span></p>
<div id="setsDiv1">

<p><select id="primesetSel" size="1">
<option value="0"> Prime Sets </option>
<option value="1"> 1 digit </option>
<option value="2"> 2 digit </option>
<option value="3"> 3 digit </option>
<option value="4"> 4 digit </option>
</select>
<button id= "nthBtn">Nth Prime</button><input id="nthPrimeIn" size="8">
<button id="collectBtn" title="Add more primes to the 'sieve'"> + </button>
<span id="nth_span">&nbsp;</span>
</p>
<p>
<button id= "primesetBtn">Between </button>
<input id= "primesetFrom" size= "12" value= "2">
<label> and </label><input id= "primesetTo" size= "12" value= "1000">
</p>

<p>
<input id= "stepIn" size= "60" value= "" readOnly= "readOnly"></p>

</div>

<div id= "setsDiv2">
<p id= "primeset_p"> &nbsp;</p>

</div>
</div>
</body>
</html>

venegal
Feb 5th, 2011, 07:50 PM
venegal would you mind commenting yours a little, because I am not sure what's going on with the numbers there (although the Sieve of Eratosthenes makes sense to me on a piece of paper, when inside a script, it's kinda confusing).


Sure thing, here you go:


// Lower bound
var start = 1000;
// Upper bound
var end = 2000;

// The numbers array should in the end hold only prime numbers
var i, j, numbers = [];
// The square root of the upper bound is stored in a variable here,
// so it won't have to be recalculated on every run through the loop
var endSqrt = Math.sqrt(end);
// Fill the numbers array with all integers up to the upper bound
// (it's ok to start with "2", since 0 and 1 aren't prime numbers anyway)
for (i = 2; i <= end; numbers[i] = i++) {};

// For each prime in the numbers array, remove all multiples of that prime from the numbers array.
// It actually doesn't loop through all primes (because they are not known yet), but through all integers,
// but if i isn't prime, execution is immediately stopped in the first line within the loop.
// It's ok to stop at the square root of the upper bound, because numbers can't have prime factors that are higher than that.
for (i = 2; i < endSqrt; i++) {
// Don't do anything if the number has already been removed, because that just means
// that it hasn't been a prime anyway,
// and the point of the Sieve is to remove multiples of *prime* numbers
// (which is equivalent to removing multiples of arbitrary numbers, just without the redundancy)
if ( ! numbers[i]) continue;
// Actually remove all multiples of the current prime from the numbers array
for (j = 2 * i; j <= end; j += i) {
delete numbers[j];
}
}

// The numbers array now contains all primes from 0 to the upper bound, and a whole bunch of empty values.
// Splice it, so it starts at the lower bound, filter it, so the empty values go away, and output.
alert(numbers.splice(start).filter(function (value) {return value;}).join(', '));



PS: No reason of arguing here about whose script is better though and how many milliseconds it takes, we have years in front of us to worry about, not a 1000s! :) People approach things differently, our minds aren't the same. Peace!

I think there is value (and learning opportunity) in comparing scripts and their efficiency. In my opinion it can be ok to trade some efficiency for readability and maintainability, since coder time is more expensive than computing time in many cases. In this case, though, I'd rather go for efficiency, since it's about a very basic algorithm that serves no real world purpose other than satisfying an interest in designing and streamlining an algorithm.

Also, even if you're really more interested in the prime numbers up to, say, 10000000, than in the algorithm itself, it *does* make a difference whether you have to wait 8 minutes for the result, or 5 seconds (notice how, as the upper bound grows, the time the slower algorithm takes grows *much* faster than the time the faster algorithm takes that makes badly designed algorithms practically unusable long before the int32 bound is reached).

Philip M
Feb 5th, 2011, 07:57 PM
Also, even if you're really more interested in the prime numbers up to, say, 10000000, than in the algorithm itself, it *does* make a difference whether you have to wait 8 minutes for the result, or 5 seconds (notice how, as the upper bound grows, the time the slower algorithm takes grows *much* faster than the time the faster algorithm takes that makes badly designed algorithms practically unusable long before the int32 bound is reached).

I don't disagree, but in the context I think that the OP (apparantly a novice) is probably interested only in prime numbers below (say) 9999999, and would prefer code which he can actually comprehend to code which is efficient. As you say, coder time is more expensive than computing time in many cases.

If you are seriously trying to find large prime numbers a different maths-orientated language is called for - not Javascript.

venegal
Feb 5th, 2011, 08:09 PM
I don't disagree, but in the context I think that the OP (apparantly a novice) is probably interested only in prime numbers below (say) 9999999, and would prefer code which he can actually comprehend to code which is efficient. As you say, coder time is more expensive than computing time in many cases.

If you are seriously trying to find large prime numbers a different maths-orientated language is called for - not Javascript.

To be honest, I don't really know what the OP is interested in. If I had to guess, I'd say he's interested in learning how one would go about generating prime numbers in an effective way. So maybe he'd been better off with a general explanation of the algorithm I used (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), but I just couldn't resist writing the thing in code.