Prime number calculation fun

public class Primes {

    public static void main(String[] args) {
    	int topPrime = 150000;
    	int current = 2;
    	int count = 0;
    	int lastPrime = 2;

    	long start = System.currentTimeMillis();

    	while (count < topPrime) {

    		boolean prime = true;

    		int top = (int)Math.sqrt(current) + 1;

    		for (int i = 2; i < top; i++) {
    			if (current % i == 0) {
    				prime = false;
    				break;
    			}
    		}

    		if (prime) {
    			count++;
    			lastPrime = current;
    		}
    		if (current == 2) {
    		 current++;
    		} else {
    			current = current + 2;
    		}
    	}

    	System.out.println("Last prime = " + lastPrime);
    	System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
    }
}

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

#!/usr/bin/env python
def iprimes_upto(limit):
    """Generate all prime numbers less then limit.

    http://stackoverflow.com/questions/188425/project-euler-problem#193605
    """
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

def sup_prime(n):
    """Return an integer upper bound for p(n).

       p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)

       where p(n) is the n-th prime.
       http://primes.utm.edu/howmany.shtml#2
    """
    from math import ceil, log
    assert n >= 13
    pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
    return int(ceil(pn))

if __name__ == '__main__':
    import sys
    max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
    primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
    print("Generated %d primes" % len(primes))
    n = 100
    print("The first %d primes are %s" % (n, primes[:n]))

$ python primes.py

Generated 153465 primes
The first 100 primes are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

class Program
{
    static void Main(string[] args)
    {
        int count = 0;
        int max = 150000;
        int i = 2;

        DateTime start = DateTime.Now;
        while (count < max)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i++;

        }
        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        if (n < 4)
            return true;
        if (n % 2 == 0)
            return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

while (count < topPrime) {

            boolean prime = true;

boolean prime;
while (count < topPrime) {

            prime = true;

class Program
{
    static void Main(string[] args)
    {
        DateTime start = DateTime.Now;

        int count = 2; //once 2 and 3

        int i = 5;
        while (count < 150000)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i += 2;

            if (IsPrime(i))
            {
                count++;
            }

            i += 4;
        }

        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        //if (n < 4)
        //return true;
        //if (n % 2 == 0)
        //return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

public class Primes
{
  // Original code
  public static void first()
  {
    int topPrime = 150003;
    int current = 2;
    int count = 0;
    int lastPrime = 2;

    long start = System.currentTimeMillis();

    while (count < topPrime) {

      boolean prime = true;

      int top = (int)Math.sqrt(current) + 1;

      for (int i = 2; i < top; i++) {
        if (current % i == 0) {
          prime = false;
          break;
        }
      }

      if (prime) {
        count++;
        lastPrime = current;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
      }
      if (current == 2) {
        current++;
      } else {
        current = current + 2;
      }
    }

    System.out.println("n-- First");
    System.out.println("Last prime = " + lastPrime);
    System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
  }

  // My attempt
  public static void second()
  {
    final int wantedPrimeNb = 150000;
    int count = 0;

    int currentNumber = 1;
    int increment = 4;
    int lastPrime = 0;

    long start = System.currentTimeMillis();

NEXT_TESTING_NUMBER:
    while (count < wantedPrimeNb)
    {
      currentNumber += increment;
      increment = 6 - increment;
      if (currentNumber % 2 == 0) // Even number
        continue;
      if (currentNumber % 3 == 0) // Multiple of three
        continue;

      int top = (int) Math.sqrt(currentNumber) + 1;
      int testingNumber = 5;
      int testIncrement = 2;
      do
      {
        if (currentNumber % testingNumber == 0)
        {
          continue NEXT_TESTING_NUMBER;
        }
        testingNumber += testIncrement;
        testIncrement = 6 - testIncrement;
      } while (testingNumber < top);
      // If we got there, we have a prime
      count++;
      lastPrime = currentNumber;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
    }

    System.out.println("n-- Second");
    System.out.println("Last prime = " + lastPrime);
    System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
  }

  public static void main(String[] args)
  {
    first();
    second();
  }
}

if (current != 2 && current % 2 == 0)
                    prime = false;
            else {
                    for (int i = 3; i < top; i+=2) {
                            if (current % i == 0) {
                                    prime = false;
                                    break;
                            }
                    }
            }

let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
    match sieve with
    | [] -> sieve
    | _ when sqrt(float(max)) < float sieve.[0] -> sieve
    | _ -> let prime = sieve.[0]
           let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
           let result = getPrimes filtered max
           prime::result        // The filter removes the prime so add it back to the primes result.

let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880


//list of calculated primes
__int64* primes;
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;

//Prints all of the calculated primes
void PrintPrimes()
{
    __int64 i;
    for(i=0; i<primeCount; i++)
    {
    	printf("%d ", primes[i]);
    }

}

//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
    register __int64 i;
    double square;
    primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
    primeCount = 0;
    arraySize = ARRAYMULT;

    //we provide the first prime because its even, and it would be convenient to start
    //at an odd number so we can skip evens.
    primes[0] = 2;
    primeCount++;



    for(i=3; i<max; i+=2)
    {
    	int j;
    	square = sqrt((double)i);

    	//only test the current candidate against other primes.
    	for(j=0; j<primeCount; j++)
    	{
    		//prime divides evenly into candidate, so we have a non-prime
    		if(i%primes[j]==0)
    			break;
    		else
    		{
    			//if we've reached the point where the next prime is > than the square of the
    			//candidate, the candidate is a prime... so we can add it to the list
    			if(primes[j] > square)
    			{
    				//our array has run out of room, so we need to expand it
    				if(primeCount >= arraySize)
    				{
    					int k;
    					__int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));

    					for(k=0; k<primeCount; k++)
    					{
    						newArray[k] = primes[k];
    					}

    					arraySize += ARRAYMULT;
    					free(primes);
    					primes = newArray;
    				}
    				//add the prime to the list
    				primes[primeCount] = i;
    				primeCount++;
    				break;

    			}
    		}

    	}

    }


}
int main()
{
    int max;
    time_t t1,t2;
    double elapsedTime;

    printf("Enter the max number to calculate primes for:n");
    scanf_s("%d",&max);
    t1 = time(0);
    CalcPrime(max);
    t2 = time(0);
    elapsedTime = difftime(t2, t1);
    printf("%d Primes found.n", primeCount);
    printf("%f seconds elapsed.nn",elapsedTime);
    //PrintPrimes();
    scanf("%d");
    return 1;
}

/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000

main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;

primes[0] = 2;
count = 1;

for(i = 3; count < TOTALPRIMES; i+= 2){
    isPrime = 1;

    //check divisiblity only with previous primes
    for(j = 0; j < count; j++){
        cpr = primes[j];
        if(i % cpr == 0){
            isPrime = 0;
            break;
        }
        if(cpr*cpr > i){
            break;
        }
    }
    if(isPrime == 1){
        //printf("Prime: %dn", i);
        primes[count] = i;
        count++;
    }


}

printf("Last prime = %dn", primes[TOTALPRIMES - 1]);
}

package demo;

import java.util.List;
import java.util.HashSet;

class Primality
{
  int current = 0;
  int minValue;
  private static final HashSet<Integer> resultSet = new HashSet<Integer>();
  final int increment = 2;
  // An obvious optimization is to use some already known work as an internal
  // constant table of some kind, reducing approaches to boundary conditions.
  int[] alreadyKown =
  {
     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
     43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
     127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
     199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
     283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
     383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
     467, 479, 487, 491, 499, 503, 509, 521, 523, 541
  };
  // Trivial constructor.

  public Primality(int minValue)
   {
      this.minValue = minValue;
  }
  List calcPrimes( int startValue )
  {
      // eliminate several hundred already known primes
      // by hardcoding the first few dozen - implemented
      // from prior work by J.F. Sebastian
      if( startValue > this.minValue )
      {
          // Duh.
          current = Math.abs( start );
           do
           {
               boolean prime = true;
               int index = current;
               do
               {
                  if(current % index == 0)
                  {
                      // here, current cannot be prime so break.
                      prime = false;
                      break;
                   }
               while( --index > 0x00000000 );

               // Unreachable if not prime
               // Here for clarity

               if ( prime )
               {
                   resultSet dot add ( or put or whatever it is )
                           new Integer ( current ) ;
               }
           }
           while( ( current - increment ) > this.minValue );
           // Sanity check
           if resultSet dot size is greater that zero
           {
              for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
             return resultSet;
           }
           else throw an exception ....
      }

package demo;

import java.util.List;
import java.util.HashSet;

class Primality
{
  int current = 0;
  int minValue;
  private static final HashSet<Integer> resultSet = new HashSet<Integer>();
  final int increment = 2;
  // An obvious optimization is to use some already known work as an internal
  // constant table of some kind, reducing approaches to boundary conditions.
  int[] alreadyKown =
  {
     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
     43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
     127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
     199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
     283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
     383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
     467, 479, 487, 491, 499, 503, 509, 521, 523, 541
  };
  // Trivial constructor.

  public Primality(int minValue)
   {
      this.minValue = minValue;
  }
  List calcPrimes( int startValue )
  {
      // eliminate several hundred already known primes
      // by hardcoding the first few dozen - implemented
      // from prior work by J.F. Sebastian
      if( startValue > this.minValue )
      {
          // Duh.
          current = Math.abs( start );
           do
           {
               boolean prime = true;
               int index = current;
               do
               {
                  if(current % index == 0)
                  {
                      // here, current cannot be prime so break.
                      prime = false;
                      break;
                   }
               while( --index > 0x00000000 );

               // Unreachable if not prime
               // Here for clarity

               if ( prime )
               {
                   resultSet dot add ( or put or whatever it is )
                           new Integer ( current ) ;
               }
           }
           while( ( current - increment ) > this.minValue );
           // Sanity check
           if resultSet dot size is greater that zero
           {
              for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
             return resultSet;
           }
           else throw an exception ....
      }

if(current % 5 == 0 )
  if(current % 7 == 0 )
  if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}


// and - new work this morning:


package demo;

/**
 *
 * Buncha stuff deleted for posting .... duh.
 *
 * @author  Author
 * @version 0.2.1
 *
 * Note strings are base36
 */
public final class Alice extends java.util.HashSet<java.lang.String>
{
    // prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
    // using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
    public static void main(java.lang.String[] args)
    {
        try
        {
            final long start=System.currentTimeMillis();
            // VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
            final java.lang.Integer upperBound=new java.lang.Integer(40000);
            int index = upperBound.intValue();

            final java.util.HashSet<java.lang.String>hashSet
            = new java.util.HashSet<java.lang.String>(upperBound.intValue());//
            // Arbitraily chosen value, based on no idea where to start.
            java.math.BigInteger probablePrime
            = new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
            do
            {
                java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
                if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
                {
                    probablePrime = nextProbablePrime;
                    if( ( index % 100 ) == 0x00000000 )
                    {
                        // System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
                        continue;
                    }
                    else
                    {
                        continue;
                    }
                }
                else
                {
                    throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
                    Integer.toString(upperBound.intValue() - index)));
                }
            }
            while(--index > 0x00000000);
            System.err.println(Long.toString( System.currentTimeMillis() - start));
        }
        catch(java.security.NoSuchAlgorithmException nsae)
        {
            // Never happen
            return;
        }
        catch(java.lang.StackOverflowError soe)
        {
            // Might happen
            System.out.println(soe.getMessage());//
            return;
        }
    }
}// end class Alice

//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
    if (count == 0)
        return 0;
    if (count == 1)
    {
        if (listPrimes != null)
        {
            if (!getLast || (count == 1))
                listPrimes.Add(2);
        }

        return count;
    }

    ulong currentSquare = 1;
    ulong nextSquare = 9;
    ulong nextSquareIndex = 3;
    ulong primesCount = 1;

    List dividers = new List();

    //Only check for odd numbers starting with 3.
    for (ulong curNumber = 3; (curNumber  (nextSquareIndex % div) == 0) == false)
                dividers.Add(nextSquareIndex);

            //Move to next square number
            currentSquare = nextSquare;

            //Skip the even dividers so take the next odd square number.
            nextSquare += (4 * (nextSquareIndex + 1));
            nextSquareIndex += 2;

            //We may continue as a square number is never a prime number for obvious reasons :).
            continue;
        }

        //Check if there is at least one divider for the current number.
        //If so, this is not a prime number.
        if (dividers.Exists(div => (curNumber % div) == 0) == false)
        {
            if (listPrimes != null)
            {
                //Unless we requested only the last prime, add it to the list of found prime numbers.
                if (!getLast || (primesCount + 1 == count))
                    listPrimes.Add(curNumber);
            }
            primesCount++;
        }
    }

    return primesCount;
}

//returns number of primes less than n
private static int getNumberOfPrimes(final int n)
{
    if(n < 2)
        return 0;
    BitSet candidates = new BitSet(n - 1);
    candidates.set(0, false);
    candidates.set(1, false);
    candidates.set(2, n);
    for(int i = 2; i < n; i++)
        if(candidates.get(i))
            for(int j = i + i; j < n; j += i)
                if(candidates.get(j) && j % i == 0)
                    candidates.set(j, false);
    return candidates.cardinality();
}