|
锁定老帖子 主题：一道简单的Java面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (3)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-02
最后修改：2011-10-02
public class Test {
public static void main(String[] args) {
for(int i = 2;i<=100;i++){
if(i%2!=0|i/2==1){
if(i%3!=0|i/3==1){
if(i%5!=0|i/5==1){
if(i%7!=0i/7==1){
System.out.println(i);
}
}
}
}
}
}
}
我是按数学理论算的，木有逻辑，别喷我！ |
| 返回顶楼 | |
|
发表时间：2011-10-06
最后修改：2011-10-06
public static void main(String[] args) {
boolean flag;
List<Integer> prime = new ArrayList<Integer>();
prime.add(2);
for (int i = 3; i < 200; i++) {
flag = true;
for (Integer num : prime) {
if (i % num == 0) {
flag = false;
break;
}
}
if(flag) {
prime.add(i);
System.out.println(i);
}
}
}
看看我的 |
| 返回顶楼 | |
|
发表时间：2011-10-06
这件事不是真的吧，楼主的意思是搞java的都不知道几本算法吧，是嘲笑搞java的算法和数据结构不行吗？
|
| 返回顶楼 | |
|
发表时间：2011-10-06
实际应用开发中，这种东西一般写成常量较好。
private static final int[] PRIME_LT_100=new int[]{2,3,5,7,11,...}; public static final boolean isPrime(n){ //折半查找 } 基本10000以内的都可以这样做。如果有人写复杂算法的一律不要。 |
| 返回顶楼 | |
|
发表时间：2011-10-13
public static void second(){
long start =System.currentTimeMillis(); //for (int i = 3; i < 6; i++) { int i = 3; while(i<6){ int j; for (j = 2; j < (int) (i); j++){ System.out.print(j+"jj. "); if (i % j == 0) { break; } } if (j > (i-1)) { System.out.println(i + " "); } i++; } long end =System.currentTimeMillis(); System.out.println(); System.out.println("time"+ (end - start)); } |
| 返回顶楼 | |
|
发表时间：2011-10-13
最后修改：2011-10-13
格式不知道怎么弄...
|
| 返回顶楼 | |
|
发表时间：2011-10-14
最后修改：2011-10-14
public static List<Integer> getPrime(long num) {
long sqrt = Math.round(Math.sqrt(num));
List<Integer> dividedList = new ArrayList<Integer>();
List<Integer> primeList = new ArrayList<Integer>();
for (int i = 2; i < num; i++) {
boolean flag = true;
for (int j = 0; j < dividedList.size(); j++) {
if (i % dividedList.get(j) == 0) {
flag = false;
break;
}
}
if (flag) {
if (i <= sqrt) {
dividedList.add(i);
}
primeList.add(i);
}
}
return primeList;
}
这个应该是可以的。时间效率上也不错，就是占用了点空间。50000的数据46毫秒 |
| 返回顶楼 | |
|
发表时间：2011-10-14
最后修改：2011-10-14
rickysun 写道 刚才用50000测了一下这两种算法，一个是297毫秒，一个耗时7875毫秒。
快速算法：
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(2);
System.out.println(2);
for (int i = 2; i <= 50000; i++) {
boolean ok = true;
for (int t : al) { //用已有质数集作判断,减少比较次数
if (i % t == 0) {
ok = false;
break;
}
if (t > i / 2) {
break;
}
}
if (ok) {
System.out.println(i);
al.add(i);
}
}
普通算法：
for(int i=2;i<=50000;i++) {
boolean ok = true;
for (int j = 2; j < i; j++) {
if(i%j==0) {
ok = false;
}
}
if(ok) System.out.println(i);
}
楼主没有必要将所有已找到的质数放入al。只要将小于等于50000开根后的最大整数的质数放入al就可以了 做了点修改 快速算法：
ArrayList<Integer> al = new ArrayList<Integer>();
long sqrt = Math.round(Math.sqrt(50000));
al.add(2);
System.out.println(2);
for (int i = 2; i <= 50000; i++) {
boolean ok = true;
for (int t : al) { //用已有质数集作判断,减少比较次数
if (i % t == 0) {
ok = false;
break;
}
if (t > i / 2) {
break;
}
}
if (ok) {
System.out.println(i);
if(i<=sqrt){
al.add(i);
}
}
}
|
| 返回顶楼 | |
|
发表时间：2011-10-14
rickysun 写道 求100以内的质数（指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。）
大家觉得这是个很难的题目吗？ 最近面试了很多人，职位是：Java开发工程师。 有人说“这个是算法题，我是搞J2EE开发的，不需要会这个题目”，此人薪资要求8K 有人说“可能专业不对口，我是搞SSH的，我Struts/Spring/Hibernate都懂。这个做不出来”，此人薪资要求8.5K。 最终有一个哥们，做了15分钟，终于给出答案了。当然是答案是错的，此人薪资要求12K。 他给的答案是：
for(int i=0;i<100;i++) {
for(int j<0;j<100;j++) {
if(i/j==0) {
break;
}
System.out.println(i);
}
}
:cry: 
我真的很无奈了。。。。。 我现在的想法是，30秒内给出答案的，直接8K以上。。。 这种做法也太挫了吧，难道不会一边遍历一边处理吗，一定要对每个元素单独处理？ 我目前刚毕业不久，绝对能在30s内给出答案，而且比上面的哪位做法强悍的多，但是我目前的工资离8k还有段距离，哎... |
| 返回顶楼 | |
|
发表时间：2011-10-19
int i,j;
for( i=1;i<=100;i++) { for(j=2;j<i;j++) { if(i%j==0) break; } if(j==i)System.out.println(i); } |
| 返回顶楼 | |
