# Finding Primes using Algorithm in MATLAB

• MATLAB
• sara_87
In summary, the conversation discusses the algorithm called the sieve of Eratosthenes, which can identify prime numbers up to a given integer N by eliminating all non-primes in that interval. The algorithm starts from a lower end and works by eliminating all numbers divisible by a prime number. A function M-file based on this algorithm for an arbitrary upper bound N can be written. The conversation also mentions a code written in Mathematica and suggests searching for "sieve of Eratosthenes" +matlab for further help.
sara_87
Hi all, i understand the following however i don't know how to put this on matlab.
any help or hints will be very appreciated.

The following algorithm enables us to identify the prime number up to a given integer N, by eliminating all non-primes in that interval. It starts from a lower end.

Start with 2, which is kept as prime. Eliminate all numbers divisible by 2 up to N.

Move then to the next bigger number that has not been eliminated, which is 3. Keep it as prime and eliminate all numbers divisible by 3 up to N.

Move then to the next bigger number that has not been eliminated, which is 5; etc.

When you reach N, all non-primes have been eliminated up to N.
Write a function M-file on the basis of this algorithm for an arbitrary upper bound N.

thank you

The algorithm is called the sieve of Eratosthenes. If you Google "sieve of Eratosthenes" +matlab you will surely find something.

thank you
i did find many pages about it but they are all very vague and i didnt understand them.
does anyone know how to do it..or at least how to start it becuase i have no idea.

The bad news is I don't know any MatLab at all. But I did write the following code in Mathematica, perhaps it will be of use for you (lines starting with // are comments):
Code:
// Set the upper bound [I]n[/I]
n = 100;
// Make a list of n elements, and declare them all to be primes
primes = Table[True, {n}];
// ... except 1 of course :)
primes[[1]] = False;
// Now go through all numbers [I]i[/I] between 2 and [I]n[/I]
For[i = 2, i <= n, i++,
// for each such [I]i[/I], go through all multiples 2[I]i[/I], 3[I]i[/I], ..., [([I]n[/I]/[I]i[/I])[I]i[/I]]
For[j = 2, j <= Floor[n/i], j++,
// such a multiple is NOT prime
primes[[j*i]] = False
]
]
// Which elements are primes (and get rid of nested lists, for aesthetic reasons)
Position[primes, True] // Flatten
Output for n = 100:
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

That's my algorithm. I think Matlab also handles lists very well, so this should be implementable. Note that this approach really does the "sieving", another possibility would be to start with an empty list and add primes as they are found.

As an aside, Mathematica can do it in one line with the somewhat cryptic but quite efficient
Complement[Range[2, n], Flatten[Outer[Times, Range[2, Sqrt[n]], Range[2, n/2]]]]
however I don't think MatLab can do it, nor that it is pedagogically very good to do

Last edited:

## 1. How does the algorithm for finding primes in MATLAB work?

The algorithm for finding primes in MATLAB utilizes the Sieve of Eratosthenes method, which involves creating a list of numbers and removing all multiples of the prime numbers from the list. The remaining numbers are then considered prime.

## 2. What is the time complexity of the prime finding algorithm in MATLAB?

The time complexity of the algorithm depends on the input size, but it can be generally considered to be O(n log log n). This means that as the input size grows, the time it takes to find primes will increase, but at a slower rate compared to other algorithms.

## 3. Can the algorithm find large primes efficiently?

The algorithm in MATLAB is efficient for finding large primes, but it may take longer for larger input sizes. It is recommended to use other methods, such as the Miller-Rabin primality test, for finding very large primes.

## 4. What is the difference between finding primes using a loop and using the built-in "isprime" function in MATLAB?

The "isprime" function in MATLAB uses a more optimized algorithm that takes advantage of the properties of prime numbers. This makes it faster and more efficient compared to using a loop to find primes.

## 5. Can the algorithm find all primes within a given range?

Yes, the algorithm in MATLAB can find all primes within a given range by specifying the starting and ending points in the input. However, the time it takes to find all primes within a large range may be longer compared to finding primes within a smaller range.

• MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
1K
• General Discussion
Replies
5
Views
658
• MATLAB, Maple, Mathematica, LaTeX
Replies
10
Views
2K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
27
Views
2K
• Programming and Computer Science
Replies
14
Views
2K
• Programming and Computer Science
Replies
28
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
637
• Engineering and Comp Sci Homework Help
Replies
1
Views
525
• Engineering and Comp Sci Homework Help
Replies
32
Views
3K