我想知道是否有解决方案来改进我的 matlab 程序，与 matlab 的素数函数相比找到素数

Question

我想知道是否有解决方案来改进我的 matlab 代码，与 matlab 的 primes 函数相比找到素数

我的程序查找素数的时间比 matlab 内置的 primes 函数要短。

也许我犯了一些编程错误，可以得到很大的改进。我不是语法师

这是我的matlab代码

clear all
format long
tic()
ending=23^2
%I find the primes >= 5 and < ending with a new sieve
% where the primes a found with pr1 pr5 pr7
% and pr11 by step 12
% and the multiples are just factor
% of primes < ending^0.5
pr1=(13:12:ending);
pr5=(5:12:ending);
pr7=(7:12:ending);
pr11=(11:12:ending);
premiers=[pr1,pr5,pr7,pr11];
pr1debut=pr1(end);
pr5debut=pr5(end);
pr7debut=pr7(end);
pr11debut=pr11(end);


premiers=sort(premiers);
multiple5=5*(3:2:premiers(length(premiers)));
multiple7=7*(3:2:premiers(length(premiers)));
multiple11=11*(3:2:premiers(length(premiers)));
multiple13=13*(3:2:premiers(length(premiers)));
multiple17=17*(3:2:premiers(length(premiers)));
multiple19=19*(3:2:premiers(length(premiers)))
multiple23=23*(3:2:premiers(length(premiers)));

multiples=[multiple5,multiple7,multiple11, multiple13,multiple17,multiple19,multiple23];


% in premiers all the numbers are primes
premiers=setdiff(premiers,multiples);


t=toc

tic
p=primes(premiers(length(premiers)));
t2=toc
result1=sum(p)-(sum(premiers)+3+2)
premiers_sauv=premiers
tic

% below i do the sieve for further ending

for n=(2:50)
ending=(11+n*12)^2;

pr1=(pr1debut:12:ending);
pr5=(pr5debut:12:ending);
pr7=(pr7debut:12:ending);
pr11=(pr11debut:12:ending);
premiers2=[pr1,pr5,pr7,pr11];
premiers2=sort(premiers2);
debut=(11+(n-1)*12)^2;
sel=(premiers2>debut);
premiers2=premiers2(sel);
a=(3:2:premiers2(end));


pr1debut=pr1(end);
pr5debut=pr5(end);
pr7debut=pr7(end);
pr11debut=pr11(end);





sel=(premiers_sauv<=(11+n*12));
sel=premiers_sauv(sel);

multiples=[];
for i=sel
    multiples=[multiples i*a];
end
premiers2=setdiff(premiers2,multiples);



premiers_sauv=[premiers_sauv premiers2];
end
t=toc

tic
p=primes(premiers_sauv(end));
t2=toc
result2=sum(p)-(sum(premiers_sauv)+3+2)

我用这个改进了 mu 代码

clear all
format long
tic()


premiers2=[5 7 11 13]
%I find the primes >= 5 and < ending with a new sieve
% where the primes a found with pr1 or2 pr7
% and pr11 by step 12
% and the multiples are just factor
% of primes < ending^0.5
n=1
pr13=1
for i=(1:100000)
pr5=5+12*i;
pr7=pr5+2;
pr11=pr7+4;
pr13=pr11+2;
sel=(premiers2 <= pr13^0.5);
pr=premiers2(sel);
if pr5/10-fix(pr5/10)~=0.5
if min(pr5./pr-fix(pr5./pr))~=0
    premiers2=[premiers2 pr5];
end
end
if pr7/10-fix(pr7/10)~=0.5
if min(pr7./pr-fix(pr7./pr))~=0
   premiers2=[premiers2 pr7];
end
end
if pr11/10-fix(pr11/10)~=0.5
if min(pr11./pr-fix(pr11./pr))~=0
   premiers2=[premiers2 pr11];
end
end
if pr13/10-fix(pr13/10)~=0.5
if min(pr13./pr-fix(pr13./pr))~=0
    premiers2=[premiers2 pr13];
end
end

end






   





t=toc

tic
p=primes(premiers2(end));
t2=toc
result=sum(p)-(sum(premiers2)+2+3)

Answer 1

这就是我理解你的代码的作用：

1. 创建最大 23² 的整数列表，不包括 2 和 3 的倍数。执行此操作的代码非常冗长，因为它重复相同的语句，每次都使用不同的硬编码整数。
2. 使用硬编码的素数列表创建一个整数列表，该整数列表是剩余素数的倍数（最多 23）。同样，代码是重复的。请注意，

   premiers(length(premiers))

   可以更好地写为

   premiers(end)

   。
3. 集合差给出的质数最多为 23²。
4. 在循环中，您现在类似地创建不包括 2 和 3 的倍数的整数列表，以及先前素数的倍数列表，并获取设置的差值。循环不断扩展查找素数的范围，结束于

   (11+50*12)^2

   (373321)。

373321确实不是一个大数字，但您的代码在MATLAB Online上运行需要48秒。内置

primes

功能需要 0.0015 秒。

您的代码速度缓慢的原因有很多。创建这些大型数字列表、将它们连接起来等等效率不高。这些列表中许多数字重复，导致重复计算。

---

这是经典筛法的快速实现。代码要短得多，不使用任何硬编码的素数，也不进行任何重复计算。它使用一个大数组，包含最大到

n

的每个整数的真值，我们想要找到小于或等于

n

的素数。

筛子从 2 开始迭代每个整数（我们知道 1 不是素数）。对于每个整数，如果它是素数（当我们到达它时仍然是

true

），那么我们将其所有倍数设置为

false

。最后，

find

找到包含

true

的索引，这些就是素数。

tic
n = (11+50*12)^2;
% An array indicating which numbers are prime. Initially every number
% is a candidate.
is_prime = true(1, n);
% 1 is not a prime
is_prime(1) = false;
% Now we loop over the remainder to find primes and nix their multiples
for ii=2:n
    if is_prime(ii)
        is_prime(ii*2:ii:end) = false;
    end
end
% Get a list of numbers that are prime
p1 = find(is_prime);
t1 = toc


tic
p2 = primes(n);
t2 = toc

assert(isequal(p1, p2))

此实现大约比内置

primes

函数慢 10 倍。我们可以通过以下方式加快速度：

1. 循环

   for ii=[2,3:2:n]

   ，（即跳过除2之外的所有偶数）。
2. 用一种在索引数组时不进行边界检查的语言编写它（在 MATLAB 中索引速度会变慢，因为它可以防止索引越界和破坏事物）。内置的

   primes

   很可能是用这种语言编写的（大多数 MATLAB 计算都是在底层用 C 或 C++ 或 Fortran 完成的）。