|
锁定老帖子 主题：一道简单的Java面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (3)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-06-20
rickysun 写道 backshadow 写道
ArrayList<Integer> al = new ArrayList<Integer>(30);
for (int i = 2; i <= 100; i++) {
boolean ok = true;
for (int t : al) { //用已有质数集作判断,减少比较次数
if (i % t == 0) {
ok = false;
break;
}
if (t > i / 2) {
break;
}
}
if (ok) {
al.add(i);
}
}
楼主啊,这是我的解法, 我曾经在面试现场解得斐波那契的3变量法和杨辉三角的一维数组法,在打游戏时候想得怪物动作的控制方法,就在昨晚还做梦想出魔兽或三国杀的成就系统解决办法,我出价不高啊,不用8k,6k就成! 哥，你是在北京吗？我就喜欢你这样的，喜欢钻研算法和技术的人。如果是只要6K，直接来我这报道吧。  哥，我替他去报到行不行？ 
for(int i=100;i>=2;i--){
for(int j=2;j<=10;j++){
if(i==j){
continue;
}
if(i%j==0){
break;
}
if(j==2){
System.out.println(i);
}
}
}
|
| 返回顶楼 | |
|
发表时间：2011-06-20
引用 哥，我替他去报到行不行？
for(int i=100;i>=2;i--){
for(int j=2;j<=10;j++){
if(i==j){
continue;
}
if(i%j==0){
break;
}
if(j==10){
System.out.println(i);
}
}
}不好意思，着急没测下，应该是if(j==10){ System.out.println(i); } |
| 返回顶楼 | |
|
发表时间：2011-06-20
public static void main(String[] args)
{
int m=0;
System.out.println(2);
for(int i=2;i<100;i++){
for(int j=2;j<i;j++){
if(i%j==0)
break;
m=j;
}
if(i==(m+1))
System.out.println(i);
}
}
|
| 返回顶楼 | |
|
发表时间：2011-06-20
liubida 写道 ppgunjack 写道 fanxiong 写道 fch415的解法介绍得比较详细。我在去除数字输出(假定大家算得都没错)后，测试时间如下：
这里贴上我的计算方法(今天才知道这叫筛法，惭愧)：
private void computeHalf(int start, int end){
int npr[] = new int[end];
StringBuffer rs = new StringBuffer();
for(int i=start; i<=end; i++){
if(i==1){
npr[i-1] = 1;
rs.append(i).append(", ");
continue;
}
if(npr[i-1]==0){
if(i>end/2){
rs.append(i).append(", ");
continue;
}
StringBuffer multiple = new StringBuffer();
int j = 2;
//System.out.println("prime:"+i);
while(j*i <=end){
int o = j*i;
npr[o-1] = o;
//multiple.append(i).append("x").append(j).append(":").append(o).append(", ");
j++;
}
//System.out.println("multiple of prime:"+multiple.toString());
rs.append(i).append(", ");
}
}
//System.out.println(rs.toString());
}
我的电脑在50w的最大值测试下，注释掉所有方法中的System.out.print(),此方法耗时44ms,backshadow&rickysun的程序11123ms,gglu的程序耗时4472ms。很遗憾的是，fch415的筛法在大于5000时就很吃力了，我没能等到结果就ctrl+c了。上面的筛法还有很大的优化空间，在更大值的计算中速度会更加明显。 抛砖引玉，希望大家一下来改！ 应该不会吧，fch415的find4应该是这个帖子最快的方法了，即使亿也是秒级时间 在小范围数据会劣于全遍历10×10的暴力乘法打点，因为质数打点判断越界次数很多，但是后期大范围数据会有优势，因为冗余计算次数更少，比较奇怪的是我之前的是依靠+质数步长来取代质数×n的打点，但计算成本居然还高一些 fch415的find4还有一些优化空间.今天研究了下. 下面是简单的测试, 我把两个方法的结果都用List来保存. 50w都在15ms左右. 100w分别是47和31. 1000w分别是578和422. 2000w分别是1266和872. 算是有一些提升吧, 问了一个数学娃,说这个方法的复杂度差不多是 O(n(logn)(loglogn)). 看还能不能进一步优化? 呵呵 我刚接触java,不知道List的操作会不会对性能有影响. 后来再测试发现,基本上50w的15ms就是因为List操作所致,真是有影响.
static void find4(int max) {
int[] num = new int[max];
int sqrt = (int) Math.sqrt(max);
for (int i = 2; i < sqrt; i++) {
if (num[i] != 1) { // 未被标记
for (int j = 2; j * i < max; j++) {
num[j * i] = 1;// 所有倍数都标记为1
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
for (int k = 3; k < max;) {
if (num[k] != 1) {
ret.add(k);
}
k += 2;
}
}
static void ListPrime(int n) {
/**
* 标记0为质数,1为合数
*/
int[] primeList = new int[n + 1];
for (int i = 2; i <= n; i++) {
if (primeList[i] == 0) {
int j = i * i;
if (j > n) break;
if (i > 2) {
while (j <= n) {
primeList[j] = 1;
j = j + i + i;
}
} else {
while (j <= n) {
primeList[j] = 1;
j = j + i;
}
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
ret.add(2);
for (int i = 3; i <= n;) {
if (primeList[i] == 0) {
//System.out.print(i + " ");
ret.add(i);
}
i += 2;
}
}
今天小猪跑来要和我比.虽然败了但是他用了个讨巧的方法, 我也借鉴来. 果然快了许多. 2000w 668ms :-)
static void ListPrime(int n) {
/**
* false为质数,true为合数
*/
boolean[] primeList = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
if (!primeList[i]) {
int j = i * i;
if (j > n)
break;
if (i > 2) {
while (j <= n) {
primeList[j] = true;
j = j + i + i;
}
} else {
while (j <= n) {
primeList[j] = true;
j = j + i;
}
}
}
}
List<Integer> ret = new ArrayList<Integer>(10000);
ret.add(2);
for (int i = 3; i <= n;) {
if (!primeList[i]) {
//System.out.print(i + " ");
ret.add(i);
}
i += 2;
}
}
|
| 返回顶楼 | |
|
发表时间：2011-06-20
int c = 0;
for (int i = 1; i < 101; i++)
{
for (int j = 1; j < i + 1; j++)
{
if ((i % j == 0) && j != 1 && j != i)
break;
else
{
if (i != 1 && i == j)
{
Response.Write(i.ToString() + "<br/>");
c++;
}
}
}
}
Response.Write(c.ToString());
楼主7.5K，我.net的干不干？ |
| 返回顶楼 | |
|
发表时间：2011-06-23
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以上。。。 楼主，真的30秒之内8K？ |
| 返回顶楼 | |
|
发表时间：2011-06-27
rickysun 写道 Bruce.Sun 写道 哥一看也愣了，想了半天没整明白啥是质数，看了楼主补充才明白需求，小整一下：
for (int i = 1; i <= 100; i++) { Boolean prime = true; // 遍历除以2-9，如果可以除尽则不是质数 for (int j = 2; j < 10; j++) { if (i % j == 0) { prime = false; break; } }// end for j if (prime) System.out.println("质数:" + i); } // end for i 不会框架的人，只会用这种笨方法，现在还记得去盛大面试的时候面试官问我不用中间变量怎么解决问题，可是习惯改不了，还是喜欢用中间变量 哈哈 正解！！ 看似简单，实则死板。 一点都不通用。。 要想求10000以内的质数怎么办？遍历除以2-99？？ |
| 返回顶楼 | |
|
发表时间：2011-06-27
最后修改：2011-06-27
我了个去的，编辑半天木有效果？
|
| 返回顶楼 | |
|
发表时间：2011-06-27
最后修改：2011-06-27
public List<Integer> GetPrime(int MaxNumber) {
List<Integer> arrIntPrime = new ArrayList<Integer>();
arrIntPrime.add(2);
boolean bolIsPrime = true;
for (int i = 3; i < MaxNumber; i++) {
// 非质数最大的除数应该是自身的平方根吧？
double dblSqrt = Math.sqrt(i);
for (int j : arrIntPrime) {
if (i % j == 0) {
bolIsPrime = false;
break;
}
if (j > dblSqrt) {
break;
}
}
if (bolIsPrime) {
arrIntPrime.add(i);
}
else{
bolIsPrime = true;
}
}
return arrIntPrime;
}
能力有限，实在想不出别的办法优化了。感觉再想提高效率只有从去掉泛型减少装箱拆箱入手了。 |
| 返回顶楼 | |
|
发表时间：2011-06-27
public class Test {
public static void main(String[] args) { for (int i = 2; i <= 100; i++) { boolean flag = true; for (int j = 2; j <= i; j++) { if ((i % j == 0) && (i != j)) { flag = false; break; } } if (flag) { System.out.println("质数：" + i); } } } } |
| 返回顶楼 | |
