Well.. I looked for a formula for it and according to my favies wikipedia: "In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be.".. so "efficiently" iterate it is! You could iterate yourself to death going through every possibility.. or try and find a better way to iterate, just less.
I figured.. welp. Let's say we have the number 100. It breaks down into 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10.. and stops there. The first number always goes up, second one always goes down. If they meet, they reverse.. and we are repeating ourselves. BUT you can try this, no matter what .. at least one of the pair of numbers is less than half. So we will ALWAYS catch the pair of multiples if we check all the numbers up to half. So what I am doing for example 100 is seeing if any number from 1-50 will divide evenly into it. The minute its divisible by any of those numbers iterating from 1 to 50, its not prime, doesn't get added to my magic list of numbers, and the loop continues to check 101.. and so on.
1031 ms to calculate is about a second, which fits into most of your attention spans out there.. so I'll take it :).
Point to note and something that was COOL. You can use (int)Math.ceil(num/2.0) to get a rounded up version of your number (ceil = ceiling, you can do Math.floor to get it rounded down.. floor is down whee). BAD thing. Don't forget your cast depending on the type of numbers being used!!!
import java.util.ArrayList;
import java.util.List;
/**
* Created by Crystal on 6/29/2015.
*/
public class Program {
public static void main(String[] args) {
// Project Euler #7
// What is the 10,001st prime number if we consider 2 the first prime number?
long start = System.nanoTime();
int num = 2;
int halfNum = 0;
boolean isPrime = true;
List primeNumbersArr = new ArrayList() {};
primeNumbersArr.add(2);
primeNumbersArr.add(3);
primeNumbersArr.add(5);
while (primeNumbersArr.size() < 10001){
isPrime = true;
if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
num++;
continue;
}
halfNum = (int)Math.ceil(num/2.0);
int i = 2;
for (; i < halfNum; i++){
if (num % i == 0){
isPrime = false;
break;
}
}
if (isPrime == true) primeNumbersArr.add(num);
num++;
}
long stop = System.nanoTime();
System.out.println(primeNumbersArr.get(10000) + " is the solution calculated in a time of " + (stop - start) / 1000000 + "ms");
}
}
104743 is the solution calculated in a time of 1031ms.
