parallel prime number code
2 views (last 30 days)
Show older comments
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 Comment
Jan
on 21 Oct 2014
Edited: Jan
on 21 Oct 2014
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?!
Answers (1)
Jan
on 21 Oct 2014
Edited: Jan
on 21 Oct 2014
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?
2 Comments
See Also
Categories
Find more on Discrete Math in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!