use*_*757 51 javascript math primes
在Javascript中我怎么能找到0到100之间的素数？我已经考虑过了,我不知道如何找到它们.我想做x%x,但我发现了明显的问题.这是我到目前为止所做的:但不幸的是,这是有史以来最糟糕的代码.
var prime = function (){
var num;
for (num = 0; num < 101; num++){
if (num % 2 === 0){
break;
}
else if (num % 3 === 0){
break;
}
else if (num % 4=== 0){
break;
}
else if (num % 5 === 0){
break;
}
else if (num % 6 === 0){
break;
}
else if (num % 7 === 0){
break;
}
else if (num % 8 === 0){
break;
}
else if (num % 9 === 0){
break;
}
else if (num % 10 === 0){
break;
}
else if (num % 11 === 0){
break;
}
else if (num % 12 === 0){
break;
}
else {
return num;
}
}
};
console.log(prime());
Ted*_*opp 69
以下是JavaScript中筛选器实现的示例:
function getPrimes(max) {
var sieve = [], i, j, primes = [];
for (i = 2; i <= max; ++i) {
if (!sieve[i]) {
// i has not been marked -- it is prime
primes.push(i);
for (j = i << 1; j <= max; j += i) {
sieve[j] = true;
}
}
}
return primes;
}
然后getPrimes(100)将返回2到100(包括)之间的所有素数的数组.当然,由于内存限制,你不能使用大参数.
Java实现看起来非常相似.
Dav*_*idS 52
这是我解决它的方式.将它从Java重写为JavaScript,请原谅我是否存在语法错误.
function isPrime (n)
{
if (n < 2) return false;
/**
* An integer is prime if it is not divisible by any prime less than or equal to its square root
**/
var q = Math.floor(Math.sqrt(n));
for (var i = 2; i <= q; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
如果数字n不能被除1和其本身之外的任何其他数字整除,则数字是一个素数.此外,检查数字[2,sqrt(n)]就足够了.
Eva*_*edy 27
这是这个脚本的现场演示:http://jsfiddle.net/K2QJp/
首先,创建一个函数来测试单个数字是否为素数.如果你想扩展Number对象,但我决定让代码尽可能简单.
function isPrime(num) {
if(num < 2) return false;
for (var i = 2; i < num; i++) {
if(num%i==0)
return false;
}
return true;
}
这个脚本遍历每个数字2到1之间的数字,并测试是否有任何数字,如果你将数字除以增量,则没有余数.如果没有余数,则不是素数.如果数字小于2,则不是素数.否则,它是素数.
然后创建一个for循环遍历数字0到100并使用该函数测试每个数字.如果是素数,则将数字输出到日志中.
for(var i = 0; i < 100; i++){
if(isPrime(i)) console.log(i);
}
我稍微修改了Sundaram算法的Sieve以减少不必要的迭代,它看起来非常快.
该算法实际上比本主题下最受欢迎的@Ted Hopp解决方案快两倍.解决084的78498素数在Chrome 55中需要20~25毫秒,在FF 50.1中需要<90毫秒.另外@ vitaly-t的下一个素数算法看起来很有趣,但结果也慢得多.
这是核心算法.可以应用分段和线程来获得极好的结果.
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i <= t; i++){
u = (n-i)/(1+2*i);
for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);循环限制说明:
就像Erasthotenes的Sieve一样,Sundaram算法的Sieve也从列表中删除了一些选定的整数.要选择跨越规则的整数是i + j +2ij≤n,其中i和j是两个索引,n是总元素的数量.一旦我们划掉每个i + j + 2ij,剩下的数字就会加倍并变为奇数(2n + 1)以显示素数列表.最后阶段实际上是偶数的自动折扣.它的证明在这里得到了很好的解释.
如果正确选择循环索引的开始和结束限制,那么Sundaram的Sieve只是快速的,这样就不会有(或最小的)冗余(多次)消除非素数.因为我们需要i和j值来计算要交叉的数字,i + j + 2ij直到n让我们看看我们如何接近.
i)所以我们必须找到i和j在它们相等时可以采用的最大值.这是2i + 2i ^ 2 = n.我们可以通过使用二次方程式来轻松地求解i的正值t = (Math.sqrt(4+8*n)-2)/4,
j)内循环索引j应该从i开始并运行到它可以与当前i值一起运行的点.仅此而已.由于我们知道i + j + 2ij = n,因此可以很容易地计算出来u = (n-i)/(1+2*i);
虽然这不会完全消除冗余交叉,但它将"大大"消除冗余.例如,对于n = 50(检查质数高达100)而不是50 x 50 = 2500,我们总共只进行30次迭代.很明显,该算法不应被视为O(n ^ 2)时间复杂度.
i j v
1 1 4
1 2 7
1 3 10
1 4 13
1 5 16
1 6 19
1 7 22 <<
1 8 25
1 9 28
1 10 31 <<
1 11 34
1 12 37 <<
1 13 40 <<
1 14 43
1 15 46
1 16 49 <<
2 2 12
2 3 17
2 4 22 << dupe #1
2 5 27
2 6 32
2 7 37 << dupe #2
2 8 42
2 9 47
3 3 24
3 4 31 << dupe #3
3 5 38
3 6 45
4 4 40 << dupe #4
4 5 49 << dupe #5
其中只有5个重复.对于n = 100,冗余度约为20%,但是对于n = 10M,冗余度增加到约300%.这意味着随着n的增长,进一步优化SoS可以更快地获得结果.因此,一个想法可能是细分,并始终保持小.
好吧..我决定进一步采取这个任务.
经过对重复交叉的仔细检查后,我开始意识到,除了i === 1案例之外,如果其中一个或两个i或j索引值都在4,7,10,13,16,19之间. .系列,生成重复的交叉.然后允许内环仅在转动时i%3-1 !== 0,从环的总数中进一步减少35-40%.因此,例如对于1M整数,嵌套循环的总转数从1.4M降至1M.哇..!我们在这里谈论的几乎是O(n).
我刚做了一个测试.在JS中,只有一个空循环计数到1B需要4000毫秒.在下面修改的算法中,找到高达100M的素数需要相同的时间.
我还实现了该算法的分段部分以推送给工人.这样我们就可以使用多个线程了.但该代码将在稍后发布.
因此,让我向您介绍修改后的Sundaram Sieve可能是最好的,不分段时.它应使用Chrome V8和Edge ChakraCore在大约15-20ms内计算0-1M之间的质数.
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i < (n-1)/3; i++) a[1+3*i] = true;
for(var i = 2; i <= t; i++){
u = (n-i)/(1+2*i);
if (i%3-1) for(var j = i; j < u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i< n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);好吧......最后我想我已经实施了一个筛子(它来自Sundaram的巧妙筛子),这是我在互联网上找到的最快的JavaScript筛子,包括"只有Eratosthenes的筛子"或者"阿特金斯的筛子".这也适用于网络工作者,多线程.
这样想吧.在用于单线程的这款简陋的AMD PC中,JS需要3,300 ms才能计数到10 ^ 9,而以下优化的分段SoS将在14,000 ms内获得50847534素数高达10 ^ 9.这意味着只计算4.25倍的操作.我认为这令人印象深刻.
你可以自己测试一下;
console.time("tare");
for (var i = 0; i < 1000000000; i++);
console.timeEnd("tare");在这里,我向您介绍最好的分段Senda of Sundaram.
"use strict";
function findPrimes(n){
function primeSieve(g,o,r){
var t = (Math.sqrt(4+8*(g+o))-2)/4,
e = 0,
s = 0;
ar.fill(true);
if (o) {
for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
for(var i = 2; i < t; i++){
s = Math.ceil((o-i)/(1+2*i));
e = (g+o-i)/(1+2*i);
if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
}
} else {
for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
for(var i = 2; i < t; i++){
e = (g-i)/(1+2*i);
if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
}
}
for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
return r;
}
var cs = n <= 1e6 ? 7500
: n <= 1e7 ? 60000
: 100000, // chunk size
cc = ~~(n/cs), // chunk count
xs = n % cs, // excess after last chunk
ar = Array(cs/2), // array used as map
result = [];
for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
result[0] *=2;
return result;
}
var primes = [];
console.time("primes");
primes = findPrimes(1000000000);
console.timeEnd("primes");
console.log(primes.length);我不确定它是否比这更好.我很想听听你的意见.
如果一个数字不能被低于所讨论数量的其他素数整除,则该数字是素数.
所以这构建了一个primes数组.测试每个新的奇数候选人n的分裂与现有的primes低于n.作为优化,它不会将偶数和前缀2视为最后一步.
var primes = [];
for(var n=3;n<=100;n+=2) {
if(primes.every(function(prime){return n%prime!=0})) {
primes.push(n);
}
}
primes.unshift(2);
| 归档时间： |
|
| 查看次数： |
148853 次 |
| 最近记录： |