parallel prime number code

Question

hadi 2014-10-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159466-parallel-prime-number-code

编辑： José-Luis 2014-10-21

在 MATLAB Online 中打开

Hi

How can I do the following code into parallel code? (prime Number)

clc

close all

clear all

%%

tic

n = input('Enter Number:');

array = 2:n;

ones = [];

for i = 1:length(array)

    if ~ array(i) == 0 
        for j = i+1: length(array) 
            if rem(array(j), array(i)) == 0 
            array(j) = 0; 
            end 
        end 
    end 
        if ~ array(i) == 0 
            ones(length(ones)+1) = array(i)
        end

end

toc

please help

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Jan 2014-10-21

编辑：Jan 2014-10-21

Please format your code properly. The nicer the code, the easier is the reading.

Do not use the name of the built-in function "ones" as name of a variable.

Instead of "if ~array(i)==0" you can write "if array(i)~=0". You check for "array(i)==0" twice, so the 2nd test can be omitted.

The iterative growing of the output "ones" wastes so much time for larger values, that a parallelization is not sufficient. Better reserve too much memory at once.

clear all is a waste of time usually. Beside other unwanted effects it deletes all breakpoints and is therefore not friendly or useful for programmers. Why the hell to teacher suggest this method such frequently?!

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2014-10-21

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/159466-parallel-prime-number-code#answer_156028

编辑：Jan 2014-10-21

在 MATLAB Online 中打开

The loop itself cannot be parallelized for the computation of one input. But you can an should vectorize the inner loop:

array = 2:n;
len   = length(array);
for k = 1:length(array)
  a = array(k);
  if a ~= 0 
     array((k + a):a:len) = 0;   % Replacement of the inner loop
  end 
end
result = array(array ~= 0);      % Collect the result outside the loop

(Please debug this, it is written in forum's editor and not tested.)

This cannot be parallelized, because the evaluation for one number depends on the former iterations.

But a parallelization is possible if you have two different inputs n and m, with m>n. But even then the total computing time is limited by the larger value m and creating the list of primes from 2 to m includes all values for the list 2 to n. Therefore this a classical example for an algorithm which does not profit from parallel computing.

Who asked you to parallel version? Does he have certain degree of humor?