通过一道简单面试题看国内java程序员基本水平

不能~举个范例 341 过得了费马，不是卡米歇尔数，但是他不是质数。

package unittest;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Test {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> zhishu = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
getzhishu(i, zhishu);
}
}

private static void getzhishu(int i, List<Integer> zhishu) {
if (i != 1 && i != 0) {
Iterator<Integer> it = zhishu.iterator();
while (it.hasNext()) {
if (i % it.next() == 0) {
return;
}
}
zhishu.add(i);
System.out.println(i);
} else {
System.out.println(i);
}
}
}

一本算法的优化：num=50000,时间：70

private static void prime(int num) {
		long start = System.currentTimeMillis();
		int m, n;
		label: for (n = 2; n <= num; n++) {
			for (m = 2; m * m <= n; m++) {
				if (n % m == 0) {
					continue label;
				}
			}
			System.out.print(n + " ");
		}
		System.out.println();
		System.out.print("时间：");
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

6N+-1算法：num=50000,时间：30

/**
	 * 6N(+-)1法
	 * 
	 * 任何一个自然数，总可以表示成为如下的形式之一： 6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
	 * 显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，
	 * 所有的素数都可以表示成6N±1的形式(N为自然数)。 根据上述分析，我们可以构造另一面筛子，只对形如6
	 * N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。
	 * 
	 * 在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为0－1的循环，则2(i+j)-1恰好就是形如6N±1的自然数。
	 * 
	 * @param num
	 */
	private static void prime2(int num) {
		long start = System.currentTimeMillis();
		for (int n = 2; n <= 3; n++) {
			System.out.print(n + " ");
		}
		label1: for (int n = 1;; n++) {
			label2: for (int m = 0; m <= 1; m++) {
				int tmp = 2 * (3 * n + m) - 1;
				if (tmp > num)
					break label1;
				for (int k = 2; k * k <= tmp; k++)
					if (tmp % k == 0)
						if (m == 0)
							continue label2;
						else
							continue label1;
				System.out.print(tmp + " ");
			}
		}
		System.out.println();
		System.out.print("时间：");
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

341 是卡米歇尔数

问题是如何判断是卡米歇尔数，使用其他测试方法，还是有漏掉的。。。

这就是大学生和 培训机构出来程序员的区别


经常遇到那种会写几句完全可以copy的代码就自己认为技术好高


我个人的看法的，搞计算机写代码只是工具，最重要的还是思维和思想

代码不会写可以学习，但是有些东西是很难学的

这个问题我认为是一个典型的业务问题，其中的业务就是“素数”
如果你对素数非常了解，那么很容易写出高效的算法
如果你第一次知道什么是素数，而且要求短时间内给出算法，那么就按照“需求”写出来就可以了
如果让你写出20W以内的类似 11,121,131,232,4554,990099这样对称的数字，不了解这是什么东西的人，10分钟，写出的算法能有多高效？？？？！！！！！

感觉LZ的方法还是慢
最快的还是占用大量内存空间筛数
根据已经筛出的素数进行再筛选
步长为每相邻两个素数的差值，也就是每次都会变
这个比固定步长肯定要快

明显不对，孪生素数（p和p+2都是素数）有无穷多个。

问题是非孪生的呢
比如 4603,4621
中间差值达到了18
筛数就只多执行一次
步长6的话中间多执行的次数肯定不止1次

这个可以实现计算复用的吧。举个例子，能被9整除的必然能被3整除，能被6整除的必然能被2或3整除，又因为筛选范围只在100内，所以只要判断当前数能否被2,3,5,7整除就可以