论坛首页 综合技术论坛

projecteuler.net第三题:素数因子

浏览 2871 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2008-06-19  
题目: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;
				}
			}
		}
	}
}
   发表时间:2008-06-19  
呵呵,这是我的解法:
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);
    }
}
0 请登录后投票
   发表时间:2008-06-19  
Eastsun 写道
呵呵,这是我的解法:
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);
    }
}


精彩!

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

能否讲讲你当时是怎么想到这些的。
0 请登录后投票
   发表时间:2008-06-19  
姜太公 写道


精彩!

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

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


呵呵,也没想太多,因为我学的就是数学,对数论方面稍稍有些了解
0 请登录后投票
   发表时间:2008-06-19  
回去恶补数学去了……
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics