how to find prime numbers by using mod function

Question

Mahome 2016-9-13

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/302969-how-to-find-prime-numbers-by-using-mod-function

编辑： George Kara 2018-9-10

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 ))

2 个评论
显示无隐藏无

John BG 2016-9-14

thanks Mohame

Stephen23 2016-9-14

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

José-Luis 2016-9-14

7
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/302969-how-to-find-prime-numbers-by-using-mod-function#answer_234688

编辑：José-Luis 2016-9-14

在 MATLAB Online 中打开

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Walter Roberson 2016-9-13

5
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/302969-how-to-find-prime-numbers-by-using-mod-function#answer_234652

在 MATLAB Online 中打开

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)

2 个评论
显示无隐藏无

John BG 2016-9-13

Walter

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

Walter Roberson 2016-9-14

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 2016-9-13

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/302969-how-to-find-prime-numbers-by-using-mod-function#answer_234655

在 MATLAB Online 中打开

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:jgb2012@sky.com jgb2012@sky.com>

7 个评论
显示 5更早的评论隐藏 5更早的评论

John D'Errico 2016-9-14

编辑：John D'Errico 2016-9-14

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.

Walter Roberson 2016-9-25

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 2018-9-10

编辑：George Kara 2018-9-10

在 MATLAB Online 中打开

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