public class primes {

	public static ArrayList<Integer> prime_list = new ArrayList<Integer>();
	public static void main(String args[]){
		int maxx = 166;

		long t0 = System.nanoTime();
		boolean[] excludearray = new boolean[maxx+1];
		for(int n=2;n<=maxx;n++){
			if(excludearray[n] == false){
				prime_list.add(n);
				for(int m=2; m<=maxx/n;m++){
					excludearray[n*m] = true;

				}
			}
		}
		//System.out.println("the primes less than 167 are:");
		//System.out.println(prime_list);
		//System.out.println("there are "   prime_list.size()   " of them");
		long time1 = System.nanoTime()-t0;

		prime_list = new ArrayList<Integer>();
		long t2 = System.nanoTime();
		boolean isPrime;
			for(int n=2; n <= maxx; n++){
			isPrime = true;
			for(int p : prime_list){
				if(n % p == 0){
					isPrime = false;
					break;
				}
			}
			if(isPrime){
				prime_list.add(n);
			}
		}
		//System.out.println("the primes less than 167 are:");
		//System.out.println(prime_list);
		//System.out.println("there are "   prime_list.size()   " of them");
		long time2 = System.nanoTime()-t2;
		System.out.println(time1 +  " nanoseconds for sieve for primes under " + (maxx+1));
		System.out.println(time2 + " nanoseconds for brute for primes under "+ (maxx+1));

the output is:

PS C:\workspace\p\src> javac primes.java
PS C:\workspace\p\src> java primes
522853 nanoseconds for sieve for primes under 167
471033 nanoseconds for brute for primes under 167

so the brute force is slightly faster for the first 38 primes, but lets look at a larger set of primes, I imagine that boolean array will do far more than make up for its creation-time-cost:

for the first 15,173 primes:

PS C:\workspace\p\src> javac primes.java
PS C:\workspace\p\src> java primes
23320782 nanoseconds for sieve for primes under 166001
992025022 nanoseconds for brute for primes under 166001

When finding the first 15,173 primes, the ‘float’ to the ‘floor of float’ comparison took 129 seconds, mod-division took 34 seconds.

specifically :

import time
t0=time.time()
prime_list = []
maxx = 166000
for n in range(2,maxx+1):
    isprime = True
    for p in prime_list:
        if n/p == int (n/p):
            isprime = False;
            break;
    if isprime == True:
        prime_list.append(n)
print("the primes less than",maxx+1,"are:")
#print(prime_list)
print("there are ", len(prime_list), "of them")
print((time.time()-t0),"secs")

vs

import time
t0=time.time()
prime_list = []
maxx = 166000
for n in range(2,maxx+1):
    isprime = True
    for p in prime_list:
        if n%p is 0;
            isprime = False;
            break;
    if isprime == True:
        prime_list.append(n)
print("the primes less than",maxx+1,"are:")
#print(prime_list)
print("there are ", len(prime_list), "of them")
print((time.time()-t0),"secs")

oh yeah, in java the the times were 1.6 seconds vs 0.98 seconds respectively.(!)

It’s nearly instant either way, but do you think in this case (first 38 primes) it makes up for the extra cost of creating/allocating the boolean array?

The density of primes decreases as you get further down the number line ( it’s like ~1/ln(n) ), so I could see this algorithm becoming a must-use for finding a larger number of primes. (although lower density of primes means higher memory use per prime for the sieve of eratosthenes as we look for larger and larger primes)

Thanks.
btw didn’t know you could iterate through an ArrayList with that syntax like you can in python with the for loop. nice.

import java.util.ArrayList;

public class primes {
	public static void main(String args[]) {
		ArrayList prime_list = new ArrayList();
		for (int n = 2; n <= 166; n++) {
			boolean isprime = true;
			for (int p : prime_list) {
				if ((n / p) == (float) n / p) {
					isprime = false;
					break;
				}
			}
			if (isprime) {
				prime_list.add(n);
			}
		}
		System.out.println("the primes less than 167 are:");
		System.out.println(prime_list);
		System.out.println("there are "  + prime_list.size() +  " of them");
	}

But really, you should use a sieve of eratosthenes:

import java.util.ArrayList;

public class primes {
	public static void main(String args[]) {
		ArrayList prime_list = new ArrayList();

		int upperBoundSquareRoot = (int) Math.sqrt(166);
		boolean[] isComposite = new boolean[166 + 1];
		for (int m = 2; m <= upperBoundSquareRoot; m  ) {
			if (!isComposite[m]) {
				prime_list.add(m);
				for (int k = m * m; k <= 166; k  = m)
					isComposite[k] = true;
			}
		}
		for (int m = upperBoundSquareRoot; m <= 166; m++)
			if (!isComposite[m])
				prime_list.add(m);

		System.out.println("the primes less than 167 are:");
		System.out.println(prime_list);
		System.out.println("there are " +  prime_list.size() +  " of them");
	}

}