Any coders in the house?

[Guest MEowmixxxx]

For fun, I wrote this to demonstrate 3 separate methods for generating large quantities of prime numbers! Let me know what you think.

 

PS. I hate java, and the last time I used it was back in high school, so pardon the sloppy sorting etc.

 

PPS. Try entering extremely small and extremely large values to see which algorithm has the advantage in both scenarios.

 

import java.util.Arrays;
import java.util.Scanner; //consider a buffered reader if you want to optimize. I'm lazy.
import java.math.BigInteger;
/* Just a quick program to demonstrate different methods to generate an array of prime numbers in a given range. A fair warning - my code can be cryptic - so your best bet it just to complie and run it yourself. I'll add in some various fluff features (ie would you like to try again, error checking to catch exceptions... but I'm not going to bother with array caching for repeat tests of methods. This is just simple tutorial and I don't want to complicate things.*/
class primalityGeneration extends Object
{
static Scanner console = new Scanner (System.in);
public static void main(String[]args) { new primalityGeneration();}

public primalityGeneration(){
System.out.print("\n\nEnter the degree to which you want to calculate: ");
int range = 100; //just a random number for the program to close without bitching upon exception.
try { //generic Try/Catch loop
range = console.nextInt();
   	}
catch(Exception ex) {System.out.println(ex);}

System.out.print("\nNow, please enter the method by which you would like to generate these primes:\n\t1: Sieve of Eratosthenes\n\t2: Brute Force\n\t3: Built-in testing through java.math.bigInteger.isProbablePrime()\n\t4: Benchmark all above methods for fastest generation.\n\n\tOption: ");
int selection = 0;
try {
selection = console.nextInt();
   	}
catch(Exception e) {System.out.println(e);}
//Case/Switch. Calls corresponding methods according to use choice.
   	switch(selection) {
       	case 1: sieve(range); break;
       	case 2: brute(range); break;
       	case 3: bigInt(range); break;
       	case 4: benchmark(range); break;
       	default: System.out.println("It would appear that this code is fail. Sorry."); System.exit(0);
       	}
   	}

   	/*The following is an example of a Sieve of Eratosthenes. In short, it builds an array of numbers and ticks off multiples of known primes as a method of speeding up the process.*/

public void sieve (int outerBounds) {
System.out.println("\n Method: Sieve.\n");
long start = System.currentTimeMillis();

       	int N = outerBounds;
   	boolean[] isPrime = new boolean[N + 1];
   	for (int i = 2; i <= N; i++) {
       	isPrime[i] = true;
   	}
   	for (int i = 2; i*i <= N; i++) {
       	if (isPrime[i]) {
           	for (int j = i; i*j <= N; j++) {
               	isPrime[i*j] = false;
           	}
       	}
   	}
   	for (int i = 2; i <= N; i++) { //print results
       	if (isPrime[i]) System.out.print(i + " ");
   	}
long result = (System.currentTimeMillis()) - start;
System.out.println("\n\n\tEfficiency of this method:\t" + result + "ms.");//calculate the amount of ms the program has been running from the point of execution
}

/* Here is just a simple brute force. I wrote this using a boolean array that tests every number in the array 1-n and either skips composite numbers or changes prime entries to TRUE*/


public void brute (int outerBounds) {
System.out.println("\n Method: Brute Force.\n");
long start = System.currentTimeMillis();
boolean [] list = new boolean [outerBounds];
for( int p = 0; p < list.length; p++) {list[p] = true;}
for( int i = 0; i < outerBounds; i++) {
for( int k = 2; k < i; k++) {
   	if((i%k) == 0) {list[i] = false; break;}}}
for(int q = 2; q < list.length; q++) { if(list[q]) {System.out.print(q + " ");}}
long result = (System.currentTimeMillis()) - start;
System.out.println("\n\n\tEfficiency of this method:\t" + result + "ms.");
}
/* This method uses the java.math.BigInteger method to sove for HUGE primes. For the algorithm, you can check out the java API. It's nuts. In short, this allows for fast generation of extremely large numbers via a probability method. For smaller sets, it is horribly inefficient.*/
public void bigInt (int outerBounds) {
System.out.println("\n Method: BigInteger.\n");
long start = System.currentTimeMillis();
BigInteger big = new BigInteger("1"); 
for(int i = 0; i < outerBounds; i++) { big = BigInteger.valueOf(i); if(big.isProbablePrime(8)) {System.out.print(i + " "); }}
long result = (System.currentTimeMillis()) - start;
System.out.println("\n\n\tEfficiency of this method:\t" + result + "ms.\n\n");
}
/* Benchmark calls all 3 methods and loggs the time it takes to execute the command for N primes.*/
public void benchmark (int range) {
System.out.println("\n\t Optional: Benchmark.\n");
/*This.. is where it gets strange.
finalr arrays are meant to hold corresponding methods to time instances.
A simpler explanation would be... I needed to arrange the times in ascending order (smallest to biggest)
so, that's all fine and dandy, but how would I be able to math them back to the corresponding methods?
The end product was two arrays and a WICKED confusing if/for/if statement set.*/
String [] finalr = new String [3];
finalr [0] = "Sieve of Eratosthenes";
finalr [1] = "Brute Force";
finalr [2] = "java.math.BigInteger";
long [] time = new long [3];
time[0] = System.currentTimeMillis();
sieve(range);
time[0] = System.currentTimeMillis() - time[0];
time[1] = System.currentTimeMillis();
brute(range);
time[1] = System.currentTimeMillis() - time[1];
time[2] = System.currentTimeMillis();
bigInt(range);
time[2] = System.currentTimeMillis() - time[2];
long temp = 0;
String strTemp = "";
//HERE IS A PERFECT Example of OVER-Engineering. WAAAY OVER.
for( int i = 2; i > 0; i--) { if (time[i] < time[i-1]) { temp = time[i-1]; time[i-1] = time[i]; time[i] = temp; strTemp = finalr[i-1]; finalr[i-1] = finalr[i]; finalr[i] = strTemp;} } if(time[2] < time[1]) {time[1] = temp; time[2] = time[1]; time[1] = temp; finalr[1] = strTemp; finalr[2] = finalr[1]; finalr[1] = strTemp;}
/*The above was my method for rearranging the times from smallest to biggest whilst keeping the corresponding method in check. This is why I didn't simply use the Arrays.sort(time); */
System.out.println("To generate all prime numbers between 2 and " + range + "... the fastest algorithm was:\n" + finalr[0] + " at a time of " + time[0] + "ms. \nThe second most efficient was:\n" + finalr[1] + " that came in at a time of " + time[1] + "ms. \nIn third, we have " + finalr[2] + " at a time of " + time[2] + "ms.");
}
}

Sorry it's not formatted - it got botched in the copypasta.

 

Here's a shot of it in action.

 

[Guest MEowmixxxx]

Followup: I just noticed a large logic error in that I include the time to call System.out.println() in my benchmark. That being said, the same amount of primes should exist per function instance, so the cost per algorithm should be identical in that the results would be equally offset... I think.

 

I'll consider recoding it after I get some sleep.

[kingdomkid1]

Power to the nerds!! Im still a nerdling, learning basic stuff with eclipse and runnin it on java, but i is still a nerd! But wow, musta taken awhile to piece together that coding meowmixxx.... Im not worthyyy, im not worthyyy, i suuuuck XD

[Tom]

god! i hate java! its such a prickey bastard. but nice useless code.