Finding Primes in Java

I have a prime-finding class here that needs improvement.

Sample result:

Number of primes?
10
2 3 5 7 11 13 17 19 23 29
Total calculation time: 6 milliseconds
Calculation time per number: 0.6 milliseconds


As more prime numbers are calculated, the calculation time per number increases.

100 primes:

Number of primes?
100
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
Total calculation time: 23 milliseconds
Calculation time per number: 0.23 milliseconds


1000 primes:

Number of primes?
1000
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
7727 7741 7753 7757 7759 7789 7793 7817 7823 7829
7841 7853 7867 7873 7877 7879 7883 7901 7907 7919
Total calculation time: 269 milliseconds
Calculation time per number: 0.269 milliseconds


Main class

`import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Number of primes?");
boolean validInput = false;
int i = 0;
while (!validInput) {
try {
i = sc.nextInt();
validInput = true;
} catch (NoSuchElementException e) {
// validInput stays false
System.out.println("That's not an integer. Try again:");
sc.next();
}
}
boolean warning = false;
if (i > 50000) {
System.out
.println("The program will not allow this many primes to be calculated!");
sc.close();
return;
} else if (i > 20000) {
System.out.println("WARNING! Large amount of memory is needed!");
warning = true;
}
if (i > 6400) {
System.out
.println("WA

Is there a better way of doing this? If so, how?

Yes, there is. Your current algorithm is \$O \left( n + \left( n \times \dfrac{n}{2} \right) + \left( \dfrac{n}{2} \right) \right) \$, or \$ O(n^{2}) \$. (The first \$n\$ is the iterating of the numbers, the \$ \left( n \times \dfrac{n}{2} \right) + \left( \dfrac{n}{2} \right) \$ is the time complexity of a triangular number.)

If you use the Sieve of Eratosthenes, which works like this...

(image courtesy of linked Wikipedia article)

you get \$ O \left(n \left( \log n \right) \left( \log \log n \right) \right) \$, which is faster. See this Stack Overflow question on how the time complexity was determined.

StackExchange Code Review Q#58864, answer score: 14