projecteuler.net第三题：素数因子

题目：The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

想了半天也没想到好的解法，凑合贴出一个，感觉很不好，抛砖引玉，期望好的解法。

import java.util.*;

public class P3{
	public static void main(String[] args){
		final int MAX = 1000000;
                /*求解一百万以内的所有素数，一百万是我臆测的，解的范围应该大致在此。*/
		short[] prime = new short[MAX];
		for(int i = 2; i < MAX; i++){
			if(prime[i] == 0){//this is a prime
				int j = 2 * i;
				while(j < MAX){
					prime[j] = -1;
					j = j + i;
				}
			}
		}

                //把这些素数放起来
		List<Integer> primeList = new LinkedList<Integer>();
		for(int i = 2; i < MAX; i++){
			if(prime[i] == 0)
				primeList.add(i);
		}
		
		long NUM = 600851475143L;
		boolean hasFactor = true;
		while(hasFactor){
			hasFactor = false;
                        //如果把List转成Array性能会不会更好些
			for(Integer i:primeList){
				if(NUM % i == 0){
					NUM = NUM / i;
					System.out.print(i + "  ");
					hasFactor = true;
					break;
				}
			}
		}
	}
}

呵呵，这是我的解法：

public class Euler003{
    public static void main(String[] args){
        long num = 600851475143L;
        long prm = 2;
        while(prm != num){
            if(num%prm == 0) num /= prm;
            else             prm += 1;
        }
        System.out.println(prm);
    }
}

精彩！

我一直想一个数可以分解成一系列素数乘积，就想找出一个素数组，从中找出一些组成这个数。根本没有想到从一个素数开始整除，下次能整除的数必然也是一个素数。

能否讲讲你当时是怎么想到这些的。

呵呵，也没想太多，因为我学的就是数学，对数论方面稍稍有些了解

回去恶补数学去了……