Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Matlab help

  1. Feb 9, 2008 #1
    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
     
  2. jcsd
  3. Feb 9, 2008 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    The algorithm is called the sieve of Eratosthenes. If you Google "sieve of Eratosthenes" +matlab you will surely find something.
     
  4. Feb 9, 2008 #3
    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.
     
  5. Feb 9, 2008 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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 (Text):

    // 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: Feb 9, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Matlab help
  1. MATLAB help (Replies: 9)

  2. MATLAB help (Replies: 2)

  3. MATLAB help (Replies: 0)

  4. MATLAB help (Replies: 7)

  5. Matlab help (Replies: 6)

Loading...