CODEWITHSUNDEEP
matlab
user162343
user162343

Reputation: 209

How to check that a number is a prime in MATLAB using "while"

I want to check that a number is a prime using the command "while", so the first thing I've got in mind was this code:

x=5;
y=2:sqrt(x);

while rem(x,y)~=0
disp('this number is prime')    

end

The thing is that I know that the "disp" inside the while loop will tell me every time that the number is prime, and I don't want that. I was trying to fix the following code for instance and get the result:

%example of repeated if's

%check if an integer is prime

x=3;

prime=1;
divisors=[];%keep track of divisors
for i=2:sqrt(x)
    if rem(x,i)==0
        prime=0;
        divisors=[divisors,i];
    end
end

if prime==1
    disp('the number is prime')
else
    disp('the number is not prime')
    disp(divisors)
end

but I don't know how to do it. Can someone help me to fix this problem please?.

NOTE: I think that for someone like me (a beginner in MATLAB ) is easier to think in the second code at first, because the problem with the first code is once you know that you want to check the remainder with every number before the one you are given to check what is supposed to be in the while loop instead of "disp('this number is prime')"

Upvotes: 1

Views: 11049

Answers (3)

norok2
norok2

Reputation: 26896

A nicer way using a variation of the trial division, extended to use wheel factorization, which is time-efficient only for smaller inputs:

function result = is_prime(num)
    num = abs(num);
    if (mod(num, 2) == 0 && num > 2) || (mod(num, 3) == 0 && num > 3)
        result = 0;
    end
    i = 5;
    while i * i <= num
        if (mod(num, i) == 0 || mod(num, (i + 2)) == 0)
            result = 0;
            break
        else
            i = i + 6;
        end
    end
    result = 1;
end

This is significantly more efficient than the naive approach.

Upvotes: 0

Ali Mirzaei
Ali Mirzaei

Reputation: 1552

There is no need to check all numbers up to given number. It could be proved that the dividable number have to be less than sqrt of the given number. you can find a proof here.

So, you can speed up your code with the following code : 

x=5;
y=2; 
isprime=true;
while (y<=sqrt(x))
   if(rem(x,y)==0)
      isprime=false;
      break;    
   end
   y = y + 1;
end

for x=5

The number is prime

for x=1000

The number is not prime

for example for a number like 10000 you will have 10000/100=100x speedup.

Upvotes: 2

rayryeng
rayryeng

Reputation: 104535

The first line of thinking is way easier.... remember what the definition of a prime number is: A prime number is prime if it can only be divisible by itself and 1. Therefore, from the number 2 up to the number, if there is at least one number that has remainder when dividing this number with the one in question, the number is not prime.

Basically, the while loop will keep incrementing up until the number or if the number has a remainder with a divisor that is being tested. Once the loop breaks, check the loop counter and see if it's equal to the number in question. If it is, then it's prime.

Something like this:

x=5;
y=2; %// Change

while rem(x,y)~=0
    y = y + 1;
end

if y == x
    disp('The number is prime');
else
    disp('The number is not prime');
end

y should not be a vector. Initialize it to 2 as that is the first number you're checking against for the remainder. As such, starting with y = 2, we check for the remainder of dividing x by y and if it isn't 0 (i.e. this not a divisor that divides into x), then check the next number by incrementing y by 1. We keep incrementing until either:

  1. There is a divisor that divides into x
  2. We have checked all numbers from y=2 up to y=x and the remainder check has failed.

So if you check this code for any prime number, it should work.... but I do warn you that using large prime numbers will make this slow. Now, situation 1 is when this is not a prime number and situation 2 is when it is a prime number.

It works for x = 5:

The number is prime

... also for x = 17:

The number is prime

... but certainly not for x = 8

The number is not prime

.... or x = 15:

The number is not prime

This is the brute force way to check if a number is prime. There are computationally efficient algorithms for checking this, such as the Euclidean Algorithm.... or if you want to use MATLAB directly, there is a function called isprime that checks every value in an vector or matrix whether each value is prime.

Upvotes: 1

Related Questions