I need a program to check prime numbers

%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

[Juan Daniel Castanier Rivas]

I think there's something wrong here, if n is divisible by i then it's not a prime number.

[Manish kumar]

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

[Walter Roberson]

@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.

[Ayesha Saleem Anjum]

This is valid answer but to long way.

Answer 1

[Andrei Bobrov]

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

[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
     
    

About Me : https://zil.ink/korosh

Answer 2

[Irfan Turk]

%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

[Walter Roberson]

After C=0 it would make sense to break the for loop.

Answer 3

[Reshma R Reghu]

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

[Walter Roberson]

That code is going to display 'not prime' twice in some cases.

Answer 4

[koushik roy]

clc
clear all
num=31;
a=primes(num);
prm=a((length(a)));
if num==prm
    out=num; % If the number is prime
end

[Walter Roberson]

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.

Answer 5

[Asastra]

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 

[John D'Errico]

@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]

Than you John! I understand now.

Best regards

Answer 6

[Rajesh Kumar]

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

[Walter Roberson]

@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?

Answer 7

[Cecilia]

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

[DGM]

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