how to find prime numbers by using mod function

I'm wondering Is it possible to find prime numbers by using mod() function?. If yes, please I need your some basic help. for example how i could find prime number from 2:100. (( without using prime function ))

[John BG]

thanks Mohame

[Stephen23]

The accepted answer is very slow. See José-Luis' answer for a much simpler and more efficient solution.

Answer 1

[José-Luis]

Much faster than @JohnBG

tic
primes_list=[];
for k=1:50000
   L=mod(k,[1:50000]);
   L2=find(L==0); 
   if length(L2)<3 
      primes_list=[primes_list k]; 
   end
end

toc

tic

primes = 2;

for ii = 2:50000
    if all(mod(ii,primes))
        primes = [primes, ii];
    end
end

toc

Elapsed time is 14.439689 seconds.

Elapsed time is 0.963569 seconds.

Note that both algorithms can easily be made almost twice as fast by taking a step of two instead of one in the loop. There are certainly smarter ways of doing this anyway.

Answer 2

[Walter Roberson]

For example,

mod(4:100, 3)

is 0 at all multiplies of 3, so where mod(4:100, 3) is 0, the value cannot be prime.

(Notice this applies when the initial value in the vector is greater than the modulus)

[John BG]

Walter

Mohame is asking for a list of primes, not a sawtooth signal

[Walter Roberson]

John:

I explained the key to understanding how mod can be used to filter multiples. This is, after all, obviously a homework question, and providing complete answers to homework questions is not good practice.

Answer 3

[John BG]

Mohame

primes_list=[]
for k=1:1:200 
   L=mod(k,[1:200]);
   L2=find(L==0); 
   if length(L2)<3 
      primes_list=[primes_list k]; 
   end
end

the list is here

primes_list
=
  Columns 1 through 5
          1.00          2.00          3.00          5.00          7.00
  Columns 6 through 10
         11.00         13.00         17.00         19.00         23.00
  Columns 11 through 15
         29.00         31.00         37.00         41.00         43.00
  Columns 16 through 20
         47.00         53.00         59.00         61.00         67.00
  Columns 21 through 25
         71.00         73.00         79.00         83.00         89.00
  Columns 26 through 30
         97.00          1.00          2.00          3.00          5.00
  Columns 31 through 35
          7.00         11.00         13.00         17.00         19.00
  Columns 36 through 40
         23.00         29.00         31.00         37.00         41.00
  Columns 41 through 45
         43.00         47.00         53.00         59.00         61.00
  Columns 46 through 50
         67.00         71.00         73.00         79.00         83.00
  Columns 51 through 55
         89.00         97.00        101.00        103.00        107.00
  Columns 56 through 60
        109.00        113.00        127.00        131.00        137.00
  Columns 61 through 65
        139.00        149.00        151.00        157.00        163.00
  Columns 66 through 70
        167.00        173.00        179.00        181.00        191.00
  Columns 71 through 73
        193.00        197.00        199.00

Mohame

if you find this answer useful would you please be so kind to mark my answer as Accepted Answer?

To any other reader, please if you find this answer of any help solving your question,

please click on the thumbs-up vote link,

thanks in advance

John BG

<mailto:[e-mail] [e-mail]>

[John D'Errico]

Um, 1 is not a prime.

[John BG]

you seem to be the only one who cares, in this MATLAB forum of practical answers, about whether 1 is included in the list of primers or is not.

And for the record, from:

Dudley, Underwood (1978), Elementary number theory (2nd ed.), W. H. Freeman and Co., ISBN 978-0-7167-0076-0, p. 10, section 2

QUOTE

_ * | .. A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself ..|*_

END OF QUOTE

[Steven Lord]

According to the definition in the quote you gave, 1 is not prime since it has only one positive divisor. Considering 1 to be prime would also have some serious implications in number theory. But since this is a MATLAB discussion forum, the question of whether 1 is prime does affect a few functions in MATLAB.

1. The output of the factor function does not contain 1 unless you call factor(1).
2. The output of the primes function does not contain 1 (even if you call it with 1 as input.)
3. The function call isprime(1) returns false.

So MATLAB does not consider 1 to be prime.

I can't speak for John D'Errico but the intent of my comment in this discussion is not to "spoil others' answers" but to correct an error I see in the given answer.

[John D'Errico]

There is no need to be nasty.

The point of my remark here being that most sources classify 1 as NOT a prime. My remark was not at all pointless. In fact, it pointed out that your answer would yield an incorrect grade from most people, since it returns 1 as a prime.

Since you seem to be fond of quotes, I'll point you to Wikipedia, the very first source that came up in a google search.

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself."

https://en.wikipedia.org/wiki/Prime_number

Even the quote that you give explicitly states that a number must have TWO distinct divisors. The number 1 has only one divisor. So perhaps I should return the very same quote to you:

QUOTE

_ * | .. A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself ..|*_

If you read that sentence very carefully, the list of numbers there is NOT a list of primes, but a list of natural numbers. Unless maybe you think that not only is 1 a prime, but so are 4 and 6. So since 1 has only 1 divisor, even your own quote explicitly denies that 1 is a prime number.

[John BG]

Mr D'Errico

whenever quoting Wikipedia, could you please quote the source behind the quote in whatever Wikipedia article pointed at?

as useful as Wikipedia is, I personally find it really useful when not knowing where to start looking, Wikipedia is 'only' the compilation of sources (academic industry experts by-passers ..).

Most of times Wikipedia articles are written by experts or people who know what they are writing about.

But sometimes Wikipedia has inaccuracies, missing data or even mistakes.

So, for the sake of giving accurate literature references to readers, whenever quoting Wikipedia articles, please also refer the book, application note, University, company, patent, whatever that is solid enough and with enough confidence to have a name, or a company signing the source.

John BG

<mailto:[e-mail] [e-mail]>

[Walter Roberson]

John BG:

https://primes.utm.edu/notes/faq/one.html

"The Primes Page: prime number research, records, and resources" (The University of Tennessee at Martin)

"Why is the number one not prime?

[...]Answer One: By definition of prime!

[...]Answer Two: Because of the purpose of primes

[...]Answer Three: Because one is a unit.

[...]Answer Four: By the Generalized Definition of Prime.

[...]"

It goes right back to Euclid's formal definition of primes.

The page itself has citations such as https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.html

You are, of course, welcome to submit your own paper to the Journal of Integer Sequences to prove that Euclid was wrong.

[George Kara]

No need to stress out guys you can just use this:

function [Primes_list]=MyPrime(n)

But still your answer is false because i get numbers like 1 4 9 etc.

    if n>=2
        Primes_list=[]
        for k=2:1:n 
           L=mod(k,[2:n]);
           L2=find(L==0); 
           if length(L2)<3 
              Primes_list=[Primes_list k];
           end
        end
    else
        disp('n must me bigger that "2"')
    end
    end

"n" is the number you want it to search to if n == 100 then it will search from [2,3,4.....98,99,100]