Question

java的一道题目，求解答。

求出1-100之间的素数，假设有n个，将这些素数存入a[n+1]的数组中。（其中n个是求出的各个素数，还有一个是随机添加其中的一个素数）
这样数组中就有相同的两个素数，写一个搜索算法，找出数组中相同的那个素数。（随机添加的素数，可手动指定，也可利用随机方法产生）
(注：存入数组后，数组中的所有元素理论上是无序的，相同的那个素数不一定就等于a[n]，而是被存入了数组中的某个角标上)

Answer 1

有个关键的问题，最后那个随机添加进去的素数是否已知？题目说“可以指定”，那就表示已知，又说“可以随机”，表示未知吧，这两种情况搜索算法复杂度是完全不同的

追问

就是1到100之间的素数中随机选择其中的一个，添加入数组，然后在把他的位置找出来，我用ArrayList直接就添加到末尾，找都不用找，哎~

追答

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Prime {
public static void main(String[] args) {
//获取100以内的素数
List<Integer> list = new ArrayList<Integer>();
list.add(2);
for (int i = 3; i < 100; i += 2) {
boolean flag = true;
for (int j = 3; j <= (int) Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
list.add(i);
}
}

//无序化得到的素数List，存入数组，并随机生成一个相同的素数
int number = list.size();
int[] primes = new int[number + 1];
int random = (int) (Math.random() * number);
primes[random] = list.get(random);
for (int i = 0; i < number + 1; i++) {
if (i != random) {
int index = (int) (Math.random() * list.size());
primes[i] = list.get(index);
list.remove(index);
}
}

//寻找相同的
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < primes.length; i++) {
if (map.put(primes[i], i) != null) {
System.out.println("相同的是" + primes[i]);
break;
}
}
}
}

Answer 2

最简单的就是两层循环遍历一下就行了
如果效率要求较高的话在考虑优化