Hi. I would love to share the source code but I have a crazy plan of selling it or something. I will out line the test I use though.

I use x as an odd number and add two every test I get through. The test is

   countdif=x%primes[counter];
   counter++;
   if (countdif==0)
   {
     prime=false;
   }

This is used for all the primes under half of the number it and if if it is a prime it adds the prime to the array. This is faster than checking by all the numbers under the number because it doesn't have to chech as many numbers (it only checks primes) and things can only be divisible by things smaller or equal to half of them.

Thanks for the interest I hope I haven't lost anyone with my explanation.



P.S. Is this acctually a hard thing to do. I had no idea and did it for the fun of it.

Wow.

Yup I was told by a good friend that I should do exactally that. It would be cool but you see the chalenge isn't the same primes are harder to find. Another problem could be that it would become to big for Processing to work with (ints only go to 2^32) except as a float which get a bit hard a appreciate. Cool Idea. Maybe you should try.

I'll think on it and maybe send you the source code if I get any where.

I am working on a 3-D FPS and a 2-D game which is like a game of life.

I don't know if they will take off.

Thanks that is useful. I'll have to update my code.

It's up to 28-mill

By the way I typed up the Fibonacci finder

heres the code for those interested.

float x=1;
float last;
float last2;
float [] fibs= new float [1];

void setup()
{
}

void draw()
{
 println (x);
 fibs=append(fibs,x);
 last=last2;
last2=x;
x+=last;
if ((x<0)||(fibs.length>187))
{
 background(255,0,0);
 saveStrings("fibs.txt",str(fibs));
exit();
}
}

Sorry but I haven't tried to make it work out all the digits of the numbers as it uses floats. I would love to see it developed so that it could though.
I hope that helps you Ellen.

Nice... Why is mine so slow???

Still it's kinda cool. What is the computer your using?

With an ancient algorithm and some efficient memory usage, I made a prime finder which finds all primes below:

• 1 million : less than a second
• 100 million : 5s
• 1 billion : 1m20s
• 10 billion : 15m
• 23 billion : half an hour

This algorithm requires a lot of memory. I had to increase my maximum available memory to 1.6Gb to be able to calculate all primes below 23 billion. Someone with more memory can probably reach a higher number with this program.

After execution of the algorithm all primes are in the computer memory. So just use the isPrime function to check whether a number is a prime.

A lot of optimizations can be applied to this code, but I made it as efficient as I can while keeping the code as readable as I can (I'm not sure if I succeeded  ).

So here's the code:

Code:

//Edit the primelimit to set the upper limit

//long primeLimit = 1000000L;//<1s 1 million
//long primeLimit = 10000000L;//<1s 10 million
long primeLimit = 100000000L;//5s 100 million
//long primeLimit = 1000000000L;//79s 1 billion
//long primeLimit = 10000000000L;//884s 10 billion
//long primeLimit = 2368000000L;//2214s

//The array which contains which numbers are primes and which are not
int[] sieve;

//Indices which indicate where a number is located in the memory
int currentArrayIndex = 0;//Inside the sieve array
int currentBitIndex = 0;  //Inside the int at that location
long currentNb = 3;       //The number we are processing

//The font
PFont font;
//Number of primes handled for each draw, to prevent animation time to interfere with calculation time
int nbRunsPerDraw = 1;
//The calculation start time
long startTime;

boolean stop = false;
int[] gIndex = new int[2];

void setup()
{
  size(800, 300);
  background(0);

  font = createFont("Arial", 48);
  textFont(font);

  int[] index = nbToIndex(primeLimit);
  sieve = new int[index[0]+1];

  startTime = millis();
  println("Limit: " + primeLimit());
}

/**
 * Check wether a number is prime or not
 * throws index out of bounds if the number is too large
 */
boolean isPrime(long number)
{
  if(number < 2) return false;
  if(number == 2) return true;
  if(number%2 == 0) return false;

  return isPrimeEff(number);
}

void draw()
{
  background(0);
  String prime = "Prime Calculator";
  text(prime, width/2-textWidth(prime)/2, height/4);

  String maxNb = "Max: " + primeLimit();
  text(maxNb, width/2-textWidth(maxNb)/2, height*3/4);

  if(currentArrayIndex < sieve.length)
  {
    String nb = ""+currentNb;
    text(nb, width/2-textWidth(nb)/2, height/2);

    //println("" + currentNb);

    long time = millis();
    for(int i = 0; i < nbRunsPerDraw; i++)
    {
      sieve();
    }
    if(millis()-time < 200)
    {
      nbRunsPerDraw = (nbRunsPerDraw > 100000000)? nbRunsPerDraw : (nbRunsPerDraw*2);
    }
  }
  else
  {
    if(!stop)
    {  
      startTime = (millis()-startTime)/1000;
      println("Found in: " + startTime + " s");
      stop = true;

      /* print all primes below 1000
       for(int i = 0; i < 1000; i++)
       {
       if(isPrime(i))
       println(i);
       }
       */
    }

    String found = "All primes found in " + startTime + " s";
    text(found, width/2-textWidth(found)/2, height/2);
  }
}

long primeLimit()
{
  long maxNb = sieve.length;
  return 2*32*maxNb;
}

void sieve()
{
  //Multiplier
  long m = 3; 

  int sieveSize = sieve.length;
  int[] index = new int[2];

  //Get the location in memory of the multiple of the current prime
  nbToIndex(m*currentNb, index);

  //Mark all multiples of the current prime number as not prime
  while(index[0] < sieveSize)
  {  
    markNonPrime(index);

    //Increment multiplier
    m += 2;      

    //Get the location in memory of the multiple of the current prime
    nbToIndex(m*currentNb, index);
  }

  findNextPrime();
}

void markNonPrime(int[] index)
{
  sieve[index[0]] |= (1<<index[1]); 
}

void findNextPrime()
{
  do
  {
    currentBitIndex = (currentBitIndex + 1)%32;
    if(currentBitIndex == 0)
    {
      currentArrayIndex += 1;
    }
    currentNb = indexToNb(currentArrayIndex, currentBitIndex);
  } 
  while(currentArrayIndex < sieve.length && !isPrimeEff(currentNb));
}

/*
 * Precondition: number >= 3 and number is odd
 */
boolean isPrimeEff(long number)
{
  nbToIndex(number, gIndex);

  return ((sieve[gIndex[0]] & (1<<gIndex[1])) == 0);
}


long indexToNb(long arrayIndex, long bitIndex)
{
  return 2*(arrayIndex*32+bitIndex)+3; 
}

/*
 * Precondition: number >= 3 and number is odd
 */
int[] nbToIndex(long number)
{
  int[] index = new int[2];
  nbToIndex(number, index);
  return index;
}

/*
 * Precondition: number >= 3 and number is odd
 */
void nbToIndex(long number, int[] index)
{
  long ind = (number-3)>>1;
  index[0] = (int)(ind>>5);
  index[1] = (int)(ind%32);
}



 

No, it's the regular sieve.
As I said, a lot of optimizations are possible, but the approach I used yields very elegant and simple code (imho).

Hi I have decided to post the source code and it would be great if people could given suggestions as to how to make it better.

PrintWriter output;
float MTM=0;
String TM;
int [] primes=new int[1];
float PR;
int x=3;
int view=0;
int lastprime;
PFont font;
boolean prime=true;
int veiwW=0;
int savergap=100;
int maxpersave=savergap;
int primeslength1;
int pps;
color alert=color(0,255,0);
float framerate=60;
int starttime;
int time;
String [] times=new String[2];

void setup()
{
 size(720,220);
background(0);
 font = loadFont("Algerian-48.vlw");
 textFont(font, 48);
      text("Loading...",40,50);
delay(5);
times= loadStrings("time.txt");
     starttime=int(times[0]);
 primes= int(loadStrings("primes.txt"));
 if(primes.length>3)
 {
 x=int(primes[primes.length-1]);
 }
 else
 {
 x=2;
 }
 maxpersave=primes.length+savergap;
 primeslength1=primes.length;
 frameRate(framerate);
 output = createWriter("data/primes.txt");
 int counter=0;
 while(counter<primes.length)
 {
   PR+=primes[counter];
   PR=PR/2;
   output.println(str(primes[counter]));
   counter++;
 }
}

void draw()
{
 time=millis()/1000;
 if (primes.length>3)
 {
 PR=(PR+(primes[primes.length-1]-primes[primes.length-2]))/2;  
 }
 delay(int(frameRate/5));
 setup_primes();
 test_primes();
    background(0);
   rect(0,height-15,width*((x%1000000)/1000000.0),15);
 if(veiwW==0)
 {
   display_primes();
 }
 if(veiwW==1)
 {
   view_primes();
 }
 if(veiwW==2)
 {
   view_stats();
 }
   if(veiwW==3)
 {
   view_clock();
 }
veiwW=veiwW%4;
 save_primes();
 delay(5);
}

void keyPressed()
{
if (keyCode==ESC)
{
save_primes();
}  
if(key==' ')
{
keyPressed=false;
veiwW++;
}
}


void setup_primes()
{
 if ((primes.length>maxpersave-2)||((primes.length==maxpersave)))
 {
   alert=color(255,0,0);
 }
 if (x>2147483647)
 {
   exit();
 }
 x++;
 x++;
 prime=true;
 fill(color(alert));
 ellipse(width-50,50,21,21);
 fill(255);
}

void test_primes()
{
 int counter;
 int countdif;
 counter=0;
 if (x%2==0)
 {
   x--;
 }
 while((primes.length>counter)&&(primes[counter]<sqrt(x+1)))
 {
   countdif=x%primes[counter];
   counter++;
   if (countdif==0)
   {
     prime=false;
   }
 }
 if ((prime)&&(x%2==1))
 {
   primes=append(primes,x);
   output.println(str(x));
   lastprime=x;
 }
}

void display_primes()
{
 pps=int((primes.length-primeslength1)/(frameCount/frameRate));
 text("last prime:"+lastprime,20,60);
 text("checking:"+x+"  PPS:"+int(pps),20,120);
 text("Found Primes:"+primes.length,20,180);
}

void save_primes()
{
 if ((primes.length>maxpersave)||(keyPressed))
 {
   maxpersave=primes.length+savergap;
   output.flush();
   alert= color(0,255,0);
   times[0]  = str(int(time+starttime));
   times[1]  = int((time+starttime)/3600.0)+":"+int((time+starttime)/60.0%60)+":"+int((time+sta
rttime)%60);
   saveStrings("data/time.txt", times);
   delay(500);
 }
 if ((time+starttime)%30==0)
 {
   times[0]  = str(int(time+starttime));
   times[1]  = int((time+starttime)/3600.0)+":"+int((time+starttime)/60.0%60)+":"+int((time+sta
rttime)%60);
   saveStrings("data/time.txt", times);
 }
}


void view_primes()
{

 view=view%primes.length;
 view=(view+primes.length)%primes.length;
 text(primes[view],40,150);
 text("Prime No# "+view%primes.length,40,50);
 text("of "+primes.length,40,100);
 rect(width-30,float(view)/float(primes.length)*height,20,20);
 if ((mousePressed)&&(mouseX>width-30)&&(mouseX<width-10))
 {
   view=int(float(mouseY)/float(height)*primes.length);
 }

 if ((keyPressed)&&(keyCode==UP))
 {
   keyPressed=false;
   view--;
 }
 if ((keyPressed)&&(keyCode==DOWN))
 {
   keyPressed=false;
   view++;
 }
}

void view_stats()
{
  MTM=(1000000-(x%1000000))/20.0/60;
 TM=str(int(MTM/60)+hour()%12)+":"+str(int(((MTM/60.0%1)*60)%60));
 text("TNM"+TM+" PTS: "+((100+primes.length-maxpersave)%100),20,50);
text( "T:"+int((time+starttime)/3600.0)+":"+int((time+starttime)/60.0%60)+":"+int((tim
e+starttime)%60),440,50);
 text("FPS:"+int(frameRate)+"  Frame Speed: "+int((frameRate/framerate)*100.0)+"%",40,100);
 text("Prime Rate:"+int(PR)+"  APR:"+int(10*float(lastprime)/float(primes.length))/10.0,40,150);

}

void view_clock()
{
 
 MTM=(1000000-(x%1000000))/40.0/60;
 TM=str(int(MTM/60))+":"+str(int((MTM/60%1)*60))+":"+str(int(((MTM/60%1)*3600)%60
));
  text("HTM:"+TM,20,50);
 translate(2*width/3,height/2);
 fill(255);
 pushMatrix();
 rotate(-PI/2.0);
   ellipse(0,0,210,210);
   fill(0);
 ellipse(0,0,200,200);
int count=0;
fill(255);
 while(count<12)
 {
pushMatrix();
rotate(count/12.0*TWO_PI);
rect(90,-3,-10,6);
if(count/12*4%1==0)
{
rect(90,-4,-10,8);
}
if(count==0)
{
rect(90,-4,-15,8);
}
count++;
popMatrix();
}
 noStroke();
 pushMatrix();
   rotate(((MTM/60/60/12%1)*60)%60*TWO_PI);
 fill(0,255,0);
 rect(0,-2.5,50,5);
 popMatrix();
   pushMatrix();
   rotate(((MTM/3600%1)*60)%60*TWO_PI);
   fill(0,255,0);
   rect(0,-2.5,90,5);
 popMatrix();
     pushMatrix();
   rotate(((MTM/60%1)*60)%60*TWO_PI);
   fill(0,0,255);
   rect(0,-1.5,90,3);
 popMatrix();
 popMatrix();
}

thanks

Alright, here's what I think...the main goal is to generate prime numbers. Once you have them generated, testing them is easy: check the list (if it's less than or equal to the largest number in your list), and if the number is on there, it's prime. You can determine by the Sieve of Eratosthenes any number up to the square of the largest number in your list. You are only limited to how large of a number your program can handle. The way I see it, that's the most efficient way of doing things. Though I like all of the frills that both your programs have to offer, I am striving to create a program that runs as fast as possible and only does the math and output to a text file.

Kyle