parallel prime number code

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

[Jan]

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]

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?

[hadi]

thanks

how to write this code with (parfor) ?

[José-Luis]

You can't. And if you could, it would return garbage.