I need a program to check prime numbers
조회 수: 422 (최근 30일)
이전 댓글 표시
%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
Walter Roberson
2022년 11월 4일
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
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
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
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
댓글 수: 1
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
댓글 수: 1
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
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
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
2022년 9월 29일
편집: John D'Errico
2022년 9월 29일
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.
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.
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
2022년 9월 29일
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
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
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에서 Loops and Conditional Statements에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!