JAVA每周一题(2)――曾经诺西的笔试题
求丑数：丑数是指那些因子只含2，3，5的数。2，3，4，5，6，8，9，10，12，15是最前面的丑数，请编写一个程序，打印出第1500个丑数。要求效率要高。
欢迎大家百度，只要能整理出尽可能快的程序就行。
----------------解决方案--------------------------------------------------------
像素数筛法。。。
不过好像题目说法有点问题，应该是素因子吧。否则，8和12都还有4这个非素数因子
[ 本帖最后由 书呆 于 2010-6-26 01:04 编辑 ]
----------------解决方案--------------------------------------------------------
程序代码：
import java.util.*;
public class Ex_2 {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<Integer>();
int i=1;
while(i<1000) {
treeSet.add(2*i);
treeSet.add(3*i);
treeSet.add(5*i);
i++;
}
Iterator it = treeSet.iterator();
int n = 1;
while(it.hasNext()) {
System.out.println(it.next());
if (n==1500)
{
break;
}
n++;
}
}
}
public class Ex_2 {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<Integer>();
int i=1;
while(i<1000) {
treeSet.add(2*i);
treeSet.add(3*i);
treeSet.add(5*i);
i++;
}
Iterator it = treeSet.iterator();
int n = 1;
while(it.hasNext()) {
System.out.println(it.next());
if (n==1500)
{
break;
}
n++;
}
}
}
[ 本帖最后由 lampeter123 于 2010-6-26 09:15 编辑 ]
----------------解决方案--------------------------------------------------------
回复 2楼 书呆
8=2×2×2，12=2×2×3，所以没错 ----------------解决方案--------------------------------------------------------
回复 3楼 lampeter123
你的程序还需要改改，因为2×i不一定是正确的，假如I=7就错误了，因为14=2×7，7不是（2，3，5）其中的一个.所有的因子都必须只能由2，3，5组成 ----------------解决方案--------------------------------------------------------
以下是引用linjx0123在2010-6-26 09:18:11的发言：
你的程序还需要改改，因为2×i不一定是正确的，假如I=7就错误了，因为14=2×7，7不是（2，3，5）其中的一个.所有的因子都必须只能由2，3，5组成
你的程序还需要改改，因为2×i不一定是正确的，假如I=7就错误了，因为14=2×7，7不是（2，3，5）其中的一个.所有的因子都必须只能由2，3，5组成
import java.util.*;
public class Ex_2 {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<Integer>();
int i=1;
while(i<1000) {
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) {
treeSet.add(2*i);
treeSet.add(3*i);
treeSet.add(5*i);
}
i++;
}
Iterator it = treeSet.iterator();
int n = 1;
while(it.hasNext()) {
System.out.println(it.next());
if (n==1500)
{
break;
}
n++;
}
}
}
修改了一下，这次对了吧，不过效率不高，有待改进 public class Ex_2 {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<Integer>();
int i=1;
while(i<1000) {
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) {
treeSet.add(2*i);
treeSet.add(3*i);
treeSet.add(5*i);
}
i++;
}
Iterator it = treeSet.iterator();
int n = 1;
while(it.hasNext()) {
System.out.println(it.next());
if (n==1500)
{
break;
}
n++;
}
}
}
----------------解决方案--------------------------------------------------------
还是不对，因为假如i=14，i%2==0,但是14=2×7，treeSet.add(2*i);就是2×2×7，所以还是错误的。这道题目用
while(i%5==0){
i=i/5;
}
while(i%3==0){
i=i/3;
}
while(i%2==0){
i=i/2;
}
这种方法解，虽然可以得到答案，但明显不是笔试的人想要的答案，这个效率最差了。
----------------解决方案--------------------------------------------------------
以下是引用linjx0123在2010-6-26 10:01:56的发言：
还是不对，因为假如i=14，i%2==0,但是14=2×7，treeSet.add(2*i);就是2×2×7，所以还是错误的。这道题目用
while(i%5==0){
i=i/5;
}
while(i%3==0){
i=i/3;
}
while(i%2==0){
i=i/2;
}
这种方法解，虽然可以得到答案，但明显不是笔试的人想要的答案，这个效率最差了。
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) //只包含2，3，5因子，已经没有7了 还是不对，因为假如i=14，i%2==0,但是14=2×7，treeSet.add(2*i);就是2×2×7，所以还是错误的。这道题目用
while(i%5==0){
i=i/5;
}
while(i%3==0){
i=i/3;
}
while(i%2==0){
i=i/2;
}
这种方法解，虽然可以得到答案，但明显不是笔试的人想要的答案，这个效率最差了。
----------------解决方案--------------------------------------------------------
顶下
----------------解决方案--------------------------------------------------------
回复 8楼 lampeter123
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) //只包含2，3，5因子，已经没有7了假如i=14或者22，33，55，那么if()的条件为true的。以14为例，这个时候treeset.add(2*i),3*i，5*i就是28，42，70.而28=2*2*7，42=2*3*7，70=5*2*7，都含有7，所以错误
----------------解决方案--------------------------------------------------------