...

View Full Version : Method of deleting elements from an array



stick_branch
10-19-2008, 07:12 AM
Hi, I was trying to put an implementation of Eratosthenes sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) into a web app. It currently stores all the values to an array primefactors. The aim is to leave the array with only prime factors left.
I know searching arrays is an expensive op that i would rather avoid, but splice doesn't seem like the fastest way. I've come to a few paths...

One, I could replace non-primes with "0" or NaN, sort, find the max, find it's position in the array, and delete all the numbers after that...

Or two, i could delete each number by searching inside the array for where it is located. My current code is:




for(i=1;i<=max;i++)
{
primefactor[add]=i;
add++;
}
squareroot=Math.sqrt(max);
for (test=2;test<=squareroot;test++)
{
limit=(max/test);
// Eliminating numbers
for (i=2;i<=limit;i++)
{
a=((i*test)-1);
d++;
primefactor.splice(a,1,0);
}}
But the obvious error in the code is that it will delete the element from the array, and on the second loop will cull the wrong numbers. Is there any other options to delete the non-prime factors or which option would be fastest? I'm sure that searching for each string would be very costly.

Or am i going about the sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) the completely wrong way. Thanks guys!

Stick.

BubikolRamios
10-19-2008, 08:17 AM
make another array,

loop thru first
another.push(whatewer u want from first array).

stick_branch
10-19-2008, 08:26 AM
make another array,

loop thru first
another.push(whatewer u want from first array).

I see how it works in theory, but for the sieve to work i have to delete values from the array to find the primes... e.g. this works:


for (test=2;test<=squareroot;test++)
{
limit=(max/test);
// Eliminating numbers
for (i=2;i<=limit;i++)
{
a=((i*test)-1);
if(primefactor[a]!=0)
{
d++;
}

primefactor.splice(a,1,0);
}}

function sortBack(b,a)
{
return a - b;
}
e=(max-d);
primefactor.sort(sortBack);
primefactor.splice(e,d);

But i'd rather kill the if loop than keep it there.

liorean
10-19-2008, 08:43 AM
Here's one way of doing the sieve:
function sieve(upto){
var
i=2,
j,
k,
o=[]; // You don't need this to be an array, it can be a regular object

if(upto<2 || upto!==(upto>>0))
throw'Argument upto should be an integer > 2';

// Set up a contigious number list from 2 to upto
do
o[i]=i;
while(upto>i++);

// Cull the list of non-primes
for(i in o){
k=i>>0; // Making sure k is an integer and not a string
j=k*k;
if(j>upto) // All remaining elements are primes
break;
do
delete o[j]; // Start culling at i squared
while((j+=k)<=upto)
}
return o;
}

oesxyl
10-19-2008, 10:00 AM
try also this:


<?xml version="1.0"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>prime tests</title>
<script type="text/javascript">//<![CDATA[
var primeset = [2, 3, 5, 7, 11, 13];

function isprime(thisnum){
var i;
thisnum = parseInt(thisnum);
if(primeset.indexOf(thisnum) == -1){
// is not in sieve, could be prime
var maxfactor = Math.round(Math.sqrt(thisnum));
var maxprime = primeset.pop();
primeset.push(maxprime);
if(maxfactor > maxprime){
// we must find all other primes between maxprime exclusive and maxfactor inclusive
for(i=maxprime+2;i<=maxfactor;i+=2){
if(isprime(i)){
primeset.push(i);
}
}
}
// now we can check if is prime
for(i in primeset){
if(thisnum &#37; primeset[i] == 0){
return false;
}
}
}
return true;
}
//]]></script>
</head>
<body>
<p><script type="text/javascript">//<![CDATA[
var p;
// for(p=160000;p<200000;p++){
for(p=1600;p<=2000;p++){
if(isprime(p)){
document.write(p + " is ");
}else{
document.write(p + " is not ");
}
document.write("prime <br/>");
}
document.write('in primeset we have:<br/>');
for(p in primeset){
document.write(primeset[p] + ", ");
}
document.write('<br/>');
//]]></script></p>
</body>

</html>

the speed could be improved, :)

best regards

oesxyl
10-19-2008, 10:05 AM
I see how it works in theory, but for the sieve to work i have to delete values from the array to find the primes... e.g. this works:

not necesarrely "delete", :) try to replace with "mark somehow", that means you can put them in a array and reuse later or something else. See the code I posted.

best regards



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum