Prime numbers elimination method(c++ vs turing)

[Homer_simpson]

finds prime numbers by elimination method. fairly quick in turing but no match for c++

Quote:

View.Set ("text:400;100000")
const top := 15000 %replace this value



var arr1 : array 1 .. top of int
var newtop, oldtop, counter := 0

for i : 1 .. top
if ((i mod 2) not= 0) and i not= 1 then
newtop += 1
arr1 (newtop) := i
end if
end for

oldtop := newtop
newtop := 0
counter := 1
loop
for i : 1 .. oldtop
if (arr1 (i) mod arr1 (counter)) not= 0 or (arr1 (i) <= arr1 (counter))
then
newtop += 1
arr1 (newtop) := arr1 (i)
end if
end for
oldtop := newtop
newtop := 0
counter += 1
exit when counter = oldtop
end loop


for i : 1 .. oldtop
put arr1 (i)
end for

vs

Quote:

#include <cstdlib>
#include <iostream>

using namespace std;

#define top 15000 //replace this value



int arr1[top];
int newtop, oldtop, counter;

int main(int argc, char *argv[])
{

for(int i= 1; i < top+1; i++)
{

if ((i % 2) != 0 &&( i != 1 ))
{
newtop += 1;
arr1 [newtop] = i;
}
}

oldtop = newtop;
newtop = 0;
counter = 1;

do{
for (int i= 1; i < oldtop+1; i++){
if (((arr1 [i] % arr1 [counter]) != 0 )|| (arr1 [i] <= arr1 [counter]))
{
newtop += 1;
arr1 [newtop] = arr1 [i];
}
}
oldtop = newtop;
newtop = 0;
counter += 1;
}while (counter != oldtop);

for(int i= 1; i < oldtop+1; i++)
cout <<arr1 [i]<<"\n";


system("PAUSE");
return EXIT_SUCCESS;
}

[DemonWasp]

Your Turing solution doesn't output 2 as a prime number. Whoops? I imagine your C++ variant has the same problem, but haven't bothered to test it.

Out of curiosity, how long does your C++ version take to run? I added put "Time Elapsed (ms) : ", Time.Elapsed() to the end of your Turing version and got numbers in the range 6700-7000 (about 7 seconds). Note that output dominates the execution time, costing 3.5-4 seconds for a top value of 15000.

Incidentally, a better algorithm can do the first 15000 primes almost instantly, though its output is different. After the "sieve" part executes, primes is filled with values where 0 means "prime" and 1 means "not prime". This has the advantage of being able to answer the question "is X prime?" very quickly and easily.

Here it is:

Turing:

View.Set ("text:400;100000") const TOP : int := 15000 put "Calculating primes up to ", TOP,"; times are approximate" % SIEVE PART var primes : array 1..TOP of int1 primes(1) := 1      % 1 is never prime for i : 2 .. TOP     if ( primes (i) = 0 ) then         for j : i*2 .. TOP by i             primes (j) := 1         end for     end if end for put "Computation Time (ms): ", Time.Elapsed() % OUTPUT PART for i : 2..TOP     if ( primes (i) = 0 ) then         put i     end if end for put "Time Elapsed (ms): ", Time.Elapsed()

In fact, in the 3000 ms your solution takes to compute with top=15000, my version can handle TOP=3000000 (yes, that's three million). It should be noted that outputting those primes to the screen will take several minutes, regardless of speed of the calculation.

[Homer_simpson]

very neat and simple idea. i didn't think of that. thanks for that =)

[Brightguy]

Though you are doing some needless work, DemonWasp. The upper bound of your outer loop could be floor(sqrt(TOP)) and the lower bound of your inner loop could be i^2.

[Homer_simpson]

good point.
now i'm calculating 100,000,000 primes in 5.980 seconds

Quote:

#include <cstdlib>
#include <iostream>
#include <time.h>
#include <math.h>

using namespace std;

#define top 100000000 //replace this value


double time1, timedif;
bool arr1[top];
int newtop, oldtop, counter;

int main(int argc, char *argv[])
{
time1 = (double) clock(); /* get initial time */
time1 = time1 / CLOCKS_PER_SEC; /* in seconds */

arr1[1]=1;
for(int i= 2; i < sqrt(top)+1; i++)
{
if (arr1[i]==0 )
{
for(int j= (i*i); j < top+1; j+=i)
{
arr1[j]=1;
}
}
}

timedif = ( ((double) clock()) / CLOCKS_PER_SEC) - time1;
printf("The elapsed time is %lf seconds\n", timedif);

for(int i= 2; i < top+1; i++)
{
if (arr1[i]==0)
{
//cout <<i<<"\n";
}
}

system("PAUSE");
return EXIT_SUCCESS;
}

[DemonWasp]

@Brightguy: I was aware that there were different bounds, but I was too lazy to look them up. Fair point, your bounds can be much narrower.

[wtd]

Homer_simpson @ Fri Dec 18, 2009 8:25 am wrote:

good point.
now i'm calculating 100,000,000 primes in 5.980 seconds

code:

#define top 100000000 //replace this value

How about instead of this, you make use of the command-line arguments?

[Homer_simpson]

meh. that wasn't really the point of this code. just wanted a good algorithm for prime number finding. but i see your point, it is a bit improper.

[Turing_Gamer]

I had to do a similar task at school. We had to check if 'input' was prime or not

I used 2 for loops...
1. 2 .. input ('i' loop)
2. 1 .. i ('j' loop)
if i rem j = 0 then
count := count + 1
end if

it count = 2 (1 and itself) then it is prime
else it is not

[i'm not sure]

Ok i had to do the same thing in school as turing_gamer my teacher actually challenged us to make it as fast as we could. My code is also similar to turing gamers and on my computer primes 1-1500 in 91 milliseconds and if i can make an exception with 2 and just add put 2 at the top of my code i can bring the speed down to 51 milliseconds. This program however can't really be tested to find the computing speed since all it does is check whether one number is prime or not, if it is it puts it and moves on to the next one. It's just my take on the simplest possible prime finding program.

var prime : int
var a : boolean := true
const top : int := 1500
for i: 2..top
for j: 2..i-1
if i mod j = 0 then
a := false
exit
end if
end for
if a = true then
put i, ", "..
else
a := true
end if
end for
put""
put "Time Elapsed (ms): ",Time.Elapsed