Matlab help

  • MATLAB
  • Thread starter sara_87
  • Start date
  • #1
763
0

Main Question or Discussion Point

Hi all, i understand the following however i dont 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
 

Answers and Replies

  • #2
CompuChip
Science Advisor
Homework Helper
4,302
47
The algorithm is called the sieve of Eratosthenes. If you Google "sieve of Eratosthenes" +matlab you will surely find something.
 
  • #3
763
0
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.
 
  • #4
CompuChip
Science Advisor
Homework Helper
4,302
47
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 :smile:
 
Last edited:

Related Threads on Matlab help

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
6
Views
7K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
Top