Problem 47

问题描述：

 

 

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

解决问题：

 

public class Problem47 {

	public static int[] elements = new int[100000];
	
	public static int find_prime_factors(int number){
		int index = 2;
		int total = 0;
		int tmp = number;
		while(number!=1){
			if(number%index==0){
				total++;
				do{
					number= number/index;
				}while(number%index==0);
				total = 1 + elements[number];
				
				number = 1;
			}
			index++;
		}
		elements[tmp]=total;
		return total;
	}
	
	public static int find_first(int times){
		int first =0;
		int begin = 20;
		int total = 0;
		
		do{
			total = 0;
			if(find_prime_factors(begin)==times){
				total++;
				for(int i=1;i<times;i++){
					if(find_prime_factors(begin+i)!=times){
						begin = begin+i+1;
						break;
					}else{
						total++;
					}
				}
				first = begin;
			}else{
				begin++;
			}
		}while(total<times);
		
		return first;
	}
	public static void main(String[] args){
		long t1 = System.currentTimeMillis();
		System.out.println(find_first(4));
		long t2 = System.currentTimeMillis();
		System.out.println(t2-t1);
	}
}