一旦您认真考虑过,计算从第一个到N的素数序列的最小必要条件是什么?我们采取我们需要的一切,丢弃不必要的东西-成功战略的秘诀。在这种情况下,有必要采取所有快速操作并丢弃所有劳动密集型操作,例如部门划分。决定通过除法运算来描述质数的人似乎在欺骗人类。千年过去了,人们仍然继续分享...
第一个代码:
public HashMap<Long, Long> serialPrimes() {
long range = Long.parseLong(this.range.getText().toString());
HashMap<Long, Long> primes = new HashMap<>(); //
HashMap<Long, ArrayList<Long>> spectres = new HashMap<>(); //
HashMap<Long, ArrayList<Long>> toppings = new HashMap<>(); //
for(long i = 2; i < range; i++){
if(toppings.keySet().contains(i)) { // , i
//
ArrayList<Long> spectre = toppings.get(i);
spectres.put(i, spectre);
toppings.remove(i);
for(long spectreValue : spectre) {
//
long topping = primes.get(spectreValue) + spectreValue;
primes.put(spectreValue, topping);
//
if(toppings.keySet().contains(topping)) {
toppings.get(topping).add(spectreValue);
} else {
ArrayList<Long> newSpectre = new ArrayList<>();
newSpectre.add(spectreValue);
toppings.put(topping, newSpectre);
}
}
} else { // , i
//
primes.put(i, i + i); // ,
//
//
ArrayList<Long> newSpectre = new ArrayList<>();
newSpectre.add(i);
toppings.put(i + i, newSpectre);
}
}
return primes;
}
现在一个解释。
, .
API P2P .
, -.
3 :
:
- , 2 ()
- T
- ,
- 2*n (, 2[4])
- 4[2]
- ,
- ( , )
, .
1.500.000. , 2 . -, 3.000.000. 96 , 14 ( , ).
216.816素数在2到3.000.000范围内。
Android的例子
PS:尽管操作很慢,但素数的范围是通过Eratosthenes的筛算得出的,或者只是为了简单起见检查单个数字。但是,当需要它们的完整顺序时,则需要按照与上述大致相同的思路进行思考。
但是筛子仍会遍历所有数字,尝试将经过测试的数字划分为它们。它唯一的“优势”是它不会在存储中间计算时浪费内存。但是,也许比通过此算法查找所有先前的质数要花费更多的时间来检查一个数字。