Building Primes (Java)

Question is from Programmingpraxis:

It is sometimes possible, starting with a prime, to add a digit to the front of the number that forms a new prime. For instance, starting from prime 7, adding 1 forms prime 17, adding 3 forms prime 317, adding 6 forms prime 6317, adding 2 forms prime 26317, and so on.

Your task is to write a program to find the largest prime that can be formed in this way.

Solution:

import java.util.*;

public class Building_Primes {
	public static void main(String[] args) {
		long begin = System.currentTimeMillis();
		//second argument defines length of prime number
		System.out.println(max(generate(7, 10)));
		long end = System.currentTimeMillis();
		System.out.println("Total execution time: "
                + ((double)(end-begin)/1000) + "s");
	}
	//generate prime numbers
	public static ArrayList<Long> generate(long n, int len){
		if(!isPrime(n))
			return null;
		String num = Long.toString(n);
		ArrayList<Long> primList = new ArrayList<Long>();
		ArrayList<Long> primList2 = new ArrayList<Long>();
		int counter = 1;

		for(int i = 1; i < 10; i++) {
			if (isPrime(Long.parseLong("" + i + num))) {
				primList.add(Long.parseLong("" + i + num));
			}
		}
		String temp;
		Iterator<Long> it;
		while( counter < len){
			it = primList.iterator();
			while(it.hasNext()) {
				temp = Long.toString(it.next());
				for(int i = 1; i < 10; i++) {
					if(isPrime(Long.parseLong("" + i + temp))){
						primList2.add(Long.parseLong("" + i + temp));
					}
				}
			}
			primList.clear();
			primList.addAll(primList2);
			primList2.clear();
			counter++;
		}
		return primList;
	}
	//find maximum
	public static long max(ArrayList<Long> a){
		long max = 0;
		Object[] nums;
		nums = a.toArray();
		for(int i = 0; i < nums.length; i++) {
			if(max < (Long) nums[i])
				max = (Long) nums[i];
		}
		return max;
	}
	//is the number prime?
	public static boolean isPrime(long n){
		boolean result = true;
		for(long i = 2; i <= Math.sqrt(n) + 1; i += 1){
			if(n % i == 0){
				result = false;
				break;
			}
		}
		return result;
	}
}

This is the output for generating largest prime number of length 11, OutPut:

99793578167
Total execution time: 1.537s
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s