浏览 2871 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2008-06-19
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; } } } } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间: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); } } |
|
返回顶楼 | |
发表时间: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); } } 精彩! 我一直想一个数可以分解成一系列素数乘积,就想找出一个素数组,从中找出一些组成这个数。根本没有想到从一个素数开始整除,下次能整除的数必然也是一个素数。 能否讲讲你当时是怎么想到这些的。 |
|
返回顶楼 | |
发表时间:2008-06-19
姜太公 写道 精彩! 我一直想一个数可以分解成一系列素数乘积,就想找出一个素数组,从中找出一些组成这个数。根本没有想到从一个素数开始整除,下次能整除的数必然也是一个素数。 能否讲讲你当时是怎么想到这些的。 呵呵,也没想太多,因为我学的就是数学,对数论方面稍稍有些了解 |
|
返回顶楼 | |
发表时间:2008-06-19
回去恶补数学去了……
|
|
返回顶楼 | |