I need a program to check prime numbers

301 次查看（过去 30 天）
Toni Clares
Toni Clares 2016-10-8
编辑： DGM 2024-2-13
%that is my programa and it doesn't work
clc
clear all
n=input('number') % Natural number that you want to know if it a prime number
i=2;
while i<=sqrt(n)
if n==0 | n==1
disp('not prime number');
elseif rem(n,i)==0
disp(n)
disp('is prime number');
break
end
i=i+1;
end
  4 个评论
显示 2更早的评论
Walter Roberson
Walter Roberson 2022-11-4
@Manish kumar
You start out dividing by 2, which is a fine test in itself. Then you divide by 3, which is fine itself too. Then you divide by 4... but we know that anything divisible by 4 is also divisible by 2, so dividing by 4 would not find anything that 2 did not already find, so it is a waste of time to divide by 4. You can therefore skip nearly half of your division tests if, after you try 2, you only try odd numbers after that.

请先登录，再进行评论。

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

采纳的回答

Andrei Bobrov
Andrei Bobrov 2016-10-8
编辑：Andrei Bobrov 2016-10-8
out = n((n(:) == 2 | rem(n(:),2)) ...
& any(rem(n(:)./([2,3:2:sqrt(max(n))]),1) ~= 0,2));
use
>> n = [2 78 53 18 97 6];
>> out = n((n(:) == 2 | rem(n(:),2)) ...
& any(rem(n(:)./([2,3:2:sqrt(max(n))]),1) ~= 0,2))
out =
2 53 97
>>
  1 个评论
Korosh Agha Mohammad Ghasemi
Korosh Agha Mohammad Ghasemi 2021-5-18
%fix [Bug for number 15 and 1 :) ]
n = [2 15 53 1 97 6]; % 1 and 15
out = n((n(:) == 2 | rem(n(:),2)) ...
& any(rem(n(:)./([2,3:2:sqrt(max(n))]),1) ~= 0,2));
out(out == 15) = []
out(out == 1) = []
>>
out =
2 53 97
About Me : https://zil.ink/korosh

请先登录，再进行评论。

更多回答（6 个）

Irfan Turk
Irfan Turk 2019-7-21
%This code find all prime numbers
%upto the entered number
clear all;
N=input('Prime Numbers until:');
if N<2
return;
elseif N==2
disp(2);
return;
end
Pr(1)=2;Pr(2)=3;Count=3;
for i=4:N
C=Check(i);
if C==1
Pr(Count)=i;
Count = Count +1;
end
end
disp(Pr);
function C=Check(i)
C=1;
for k=2:(ceil(sqrt(i)))
if mod(i,k)==0
C=0;
end
end
end
Reshma R Reghu
Reshma R Reghu 2021-11-26
编辑：Walter Roberson 2021-11-26
n=input('number')
flag=0;
for i=2:n/2
r=rem(n,i);
if r==0
flag=1;
disp('not prime')
end
end
if flag==1
disp('not prime')
else
disp('prime')
end
koushik roy
koushik roy 2019-9-20
clc
clear all
num=31;
a=primes(num);
prm=a((length(a)));
if num==prm
out=num; % If the number is prime
end
  1 个评论
Walter Roberson
Walter Roberson 2019-9-20
编辑：Walter Roberson 2019-9-20
Note that a(length(a)) would be the same as a(end) in the case of vector a
Your code does not define out if num==prm is false.
Your code appears to be operating by checking whether primes(num) ends in num . But if you are permitted to use primes() then just use isprime(num) instead of going to that work.

请先登录，再进行评论。

Asastra
Asastra 2020-6-12
编辑：Asastra 2020-6-13
Old question but still interesting.
I made this code and compared it to isprime. I found that it is faster than isprime for quite a large number ( I do knot for a very large number).
It is interesting to know what algorithm is used by "isprime" built in function.
=====
clear all
clc
n=100000007 %number to check
%this for built-in isprime
tic
a = isprime(n);
if a==1
disp('prime')
else
disp('not prime')
end
toc
%this for alternative code
%a function to decide a number is prime or not
tic
b= isPrime(n);
if b==1
disp('prime')
else
disp('not prime')
end
toc
%this is the function of isPrime
function isprima = isPrime(n)
b = mod(n,2);
if n==1 || n==-1
isprima=0;
elseif n==2 || n==-2
isprima=1;
elseif b==0
isprima=0;
elseif b>0
for m = 3:2:sqrt(abs(n)) %instead of i = 3:2:(n-1)
b = mod(n,m);
if b==0
isprima=0;
return
end
end
isprima=1;
endif
  2 个评论
John D'Errico
John D'Errico 2022-9-29
编辑：John D'Errico 2022-9-29
@Asastra
I just saw your answer. In it, you make an interesting point, that your code is faster than isprime, at least for a smallish number.
If you wanted to learn the algorithm used by isprime itself, do this:
type specfun/isprime
there you will see the code used. isprime is itself just written in MATLAB code. Note that this is a different algorithm used by sym/isprime, where I would expect to see a MIller-Rabin method employed.
https://en.wikipedia.org/wiki/Miller–Rabin_primality_test
Again, specfun/isprime is much simpler. In fact, it is vaguely similar to the code you used, but your code will be pretty slow for a large number. For example, how fast will your code execute as a test of this number?
X = 2251799813685269;
timeit(@() isprime(X))
ans =
0.1769114914865
But, now I'll try your code. I had to modify it, as the code you wrote is not actually valid MATLAB syntax. As well, I made it into a function, to allow me to test the time accurately.
timeit(@() altIsPrime(X))
ans =
1.3953656884865
So your code is quite a bit slower than is isprime, on a pretty large number. Why is that the case? And why is your code pretty fast for most COMPOSITE small numbers?
The isprime code uses the primes function, to generate all primes less than sqrt(N). It does that in advance. Whereas your code merely does a test divide by each odd integer less than sqrt(N). And it stops as soon as it can. So your code will be efficient for a composite number that is divisible by some smallish prime factor, as it will stop quickly when possible, and it never needs to compute that relatively large set of primes in advance. But it will be poor when applied to a large number, that does happen to truly be prime.
Is one code better tha nthe other? Really, the question is moot, since isprime is pretty fast, for even numbers as large as 2^53-1, which would be its effective limit. And really, isprime for numbers that "small" is pretty much a toy. Anyone who really cares about large primes would not bother with numbers that small. (For example, in my current work, I'm working with numbers with tens of thousands or hundreds of thousands of decimal digits. Even an efficient test on such a number will take minutes or hours to run.)
I've attached my version of altIsPrime to this comment. It is identically your code, minus the invalid syntax, and I made it a function.
Asastra
Asastra 2022-9-30
Than you John! I understand now.
Best regards

请先登录，再进行评论。

Rajesh Kumar
Rajesh Kumar 2022-9-29
编辑：Walter Roberson 2022-9-29
x=input ('enter the number you want to check for prime number')
if x<=1
disp ('not prime number')
Prime No = [Prime_number counter];
end;
Counter = Counter - 1;
end;
>> prime_numbers = sort (prime_numbers);
>> Prime_numbers
  1 个评论
Walter Roberson
Walter Roberson 2022-9-29
@Rajesh Kumar
Prime No = [Prime_number counter];
It is not valid to have a space inside a variable name in MATLAB.
You have not initialized counter used on that line.
Counter = Counter - 1;
Remember MATLAB is case sensitive, so counter and Counter would be different variables.
It is not clear what Prime_number is here. Is it a variable that you forgot to intialize? Is it a function that takes no arguments?
Where is your code testing to see whether any particular value is prime?
What should the program do if the user enters a vector of values?

请先登录，再进行评论。

Cecilia
Cecilia 2024-2-12
x = randi([1, 100000]); %a random integer between 1 and 100000 inclusively.
%start writing your code here
%Do not overwrite the value of "x"
prime = primes(100000); % lists all prime numbers <= 100,000
if (ismember (x,prime)) % determine if the random x is found within the "prime" list
result = true;
else
result = false;
end
  1 个评论
DGM
DGM 2024-2-13
编辑：DGM 2024-2-13
So you're telling me that 100003 isn't prime?
Sure constructing a primes list might be part of a smart routine, but in that sense, this is an incomplete answer, so why is it here?
Also
if (ismember (x,prime)) % determine if the random x is found within the "prime" list
result = true;
else
result = false;
end
is exactly the same thing as
result = ismember(x,prime);
but if you simplify the answer further, it becomes really apparent how flawed it is.
result = ismember(x,primes(100000)); % all the less obfuscation

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by