I need a program to check prime numbers

624 views (last 30 days)
%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 Comments
Walter Roberson
Walter Roberson on 4 Nov 2022
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.
Ayesha Saleem Anjum
Ayesha Saleem Anjum on 26 Apr 2023
This is valid answer but to long way.

Sign in to comment.

Accepted Answer

Andrei Bobrov
Andrei Bobrov on 8 Oct 2016
Edited: Andrei Bobrov on 8 Oct 2016
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 Comment
Korosh Agha Mohammad Ghasemi
%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

Sign in to comment.

More Answers (6)

Irfan Turk
Irfan Turk on 21 Jul 2019
%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 on 26 Nov 2021
Edited: Walter Roberson on 26 Nov 2021
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 Comment
Walter Roberson
Walter Roberson on 26 Nov 2021
That code is going to display 'not prime' twice in some cases.

Sign in to comment.


koushik roy
koushik roy on 20 Sep 2019
clc
clear all
num=31;
a=primes(num);
prm=a((length(a)));
if num==prm
out=num; % If the number is prime
end
  1 Comment
Walter Roberson
Walter Roberson on 20 Sep 2019
Edited: Walter Roberson on 20 Sep 2019
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.

Sign in to comment.


Asastra
Asastra on 12 Jun 2020
Edited: Asastra on 13 Jun 2020
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 Comments
John D'Errico
John D'Errico on 29 Sep 2022
Edited: John D'Errico on 29 Sep 2022
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.
Asastra
Asastra on 30 Sep 2022
Than you John! I understand now.
Best regards

Sign in to comment.


Rajesh Kumar
Rajesh Kumar on 29 Sep 2022
Edited: Walter Roberson on 29 Sep 2022
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 Comment
Walter Roberson
Walter Roberson on 29 Sep 2022
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?

Sign in to comment.


Cecilia
Cecilia on 12 Feb 2024
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 Comment
DGM
DGM on 13 Feb 2024
Edited: DGM on 13 Feb 2024
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

Sign in to comment.

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!