MATLAB求100000以内的素数,用并行算法

问题描述：

MATLAB求100000以内的素数,用并行算法
在源程序的基础上改,简单的把for改成parfor会报错,最好能有任务的分割,源程序如下：
tic
n=100000;
p = 1:2:n; % 找出奇数,因为除了2的所有素数都是奇数
q = length(p);
p(1) = 2; % 第一个素数为2
for k=3:2:sqrt(n)
if p((k+1)/2) % 如果p((k+1)/2)也就是p中原本应该等于k的那个数不为0的话
p((k+1)/2+k:k:q)=0;
% 这句的作用就是把p中所有能被k整除的数设为0,但不包括k本身.
% (k+1)/2是奇数k在p中的位置,(k+1)/2+k代表p中除了k本身之外的第二个能被k整除的数的位置,依此类推
end
end
p=p(p>0); % 把等于0的,也就是原来位置上的数是合数的去掉
fprintf('%d以内的素数有：\n',n);
q=length(p);
for k=1:8:q
fprintf('%5d',p(k:min(q,k+12))); % 每行输出13个数
fprintf('\n');
end
toc

1个回答分类：数学 2014-10-22

问题解答：

我来补答

能够用parfor并行法计算的算法
每次循环都是独立的,不依赖于其他循环的运算结果
所以循环中使用到的变量不会被其他循环改变
简单来说,假如有个循环i=1:n能够并行运算,
那么循环是不依赖与顺序的,i=1：n,i可以取n个值,值n个值无论先计算哪个都可以
这样才能并行运算
而你计算素数的算法是明显的筛子法
第一个素数是2,筛掉2的倍数
最小的3是素数,晒掉3的倍数
最小的5是素数,筛掉5的倍数
.
因为每次以最小的未被筛掉的数为新的素数,所以必须按照从小到大的顺序筛选,
所以不能用parfor并行计算
对于计算n以内素数来说,筛选法是比较快的,
然而其每一步运算需要用到之前的运算,所以不能用parfor并行运算
最简单的寻找素数的算法是试除法,
只要一个整数x不能够被2到sqrt(x)之间的整数整除,那他就是素数
这样的算法是比较慢的但是判断每个数是否是素数是独立的,可以用parfor并行计算
下面是用最简单的试除法寻找n以内的素数的代码
分别用了并行parfor和非并行for计算
为了显示差距,将n提高到1000000
matlabpool 2
n=1e6;
p=1:n;q=1:n;
p(1)=0;q(1)=0;
tic
parfor ii=2:n
if any(rem(ii,2:sqrt(ii))==0)
p(ii)=0;
end
end
p=p(p>0);
toc
tic
for ii=2:n
if any(rem(ii,2:sqrt(ii))==0)
q(ii)=0;
end
end
q=q(p>0);
toc
matlabpool close
Starting matlabpool using the 'local' configuration ... connected to 2 labs.
Elapsed time is 19.124382 seconds.
Elapsed time is 28.132064 seconds.
Sending a stop signal to all the labs ... stopped.
双核运行parfor运行了19.12秒,一般for运行了28.13秒
表示parfor是能提高一点效率
但是效率远没有筛选法来得高

展开全文阅读