Circular Primes

Matlab. This was one of the assignments in the Matlab course I took. I developed an algorithm to find total number of circular primes under a positive integer as input.

Question: Write a function called circular_primes that finds the number of circular prime numbers smaller than n, where n is a positive integer scalar input argument. For example, the number, 197, is a circular prime because all rotations of its digits: 197, 971, and 719, are themselves prime. For instance, there are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. It is important to emphasize that rotation means circular permutation not all possible permutations.

Solution: My approach to solve it was divide and conquer approach. Firstly, I checked one digit prime numbers. Then, I deleted all primes whose digits include 0,2,4,5,6,8 because those integers would make the prime divisible by either 2 or 5 when rotated. I called it “simplification stage”, and nested loop algorithm was faster than built-in “strfind” function. While checking permutations of each prime left to see if they are circular primes or not, non-circular primes were indexed as zero. At its final stage, all of zeros was deleted, and all circular primes were left.

function output = circular_primes(n) 
tic
 %First Stage - for one digit prime numbers at the beginning 

if n > 0 && n <= 10
   prime = primes(n-1);
   output = length(prime); 
   return
end 

 %Simplification Stage
 %Deleting all primes whose digits include 0,2,4,5,6,8 for n > 10

prime = primes(n-1);
for i = 5:length(prime)        %for n > 10
    x = num2str(prime(i));   
    for j = 1:length(x)        %faster than strfind function
        if x(j)=='0' || x(j)=='2' || x(j)=='4' || x(j)=='5' || x(j)=='6' || x(j)=='8'
            prime(i) = 0;      %indexing non-circular primes with zero
            break
        end 
    end
end    
new_prime = prime(prime~=0);   %the new prime array after simplifying

 %Next Stage - checking permutations of each prime for being circular prime

for i = 5:length(new_prime)    %starting with two digits primes, newprime(5)
    number = new_prime(i);     %finding permutations of the prime
    y = num2str(number);
    k = length(y);
    for j = 1:k-1             
        y = circshift(y,1);    %shifting mechanism by circshift function
        z = str2num(y);

        %z = [y y(1)];         %alternative shifting mechanism by str-num method
        %z = str2num(z);       
        %z = z - str2num(y(1))*10^k;
        %y = num2str(z);   

        if isprime(z) == 0     %checking if number is prime or not
            new_prime(i) = 0;  %indexing non-circular primes with zero
            break              %breaking out for next permutation of prime
        end    
    end
end  

 %Final Stage - deleting all zeros 

last_prime = new_prime(new_prime~=0);
output = length(last_prime);
toc
end

function output = circular_primes(n)

tic

%First Stage - for one digit prime numbers at the beginning

if n > 0 && n <= 10

prime = primes(n-1);

output = length(prime);

return

end

%Simplification Stage

%Deleting all primes whose digits include 0,2,4,5,6,8 for n > 10

prime = primes(n-1);

for i = 5:length(prime) %for n > 10

x = num2str(prime(i));

for j = 1:length(x) %faster than strfind function

if x(j)=='0' || x(j)=='2' || x(j)=='4' || x(j)=='5' || x(j)=='6' || x(j)=='8'

prime(i) = 0; %indexing non-circular primes with zero

break

end

new_prime = prime(prime~=0); %the new prime array after simplifying

%Next Stage - checking permutations of each prime for being circular prime

for i = 5:length(new_prime) %starting with two digits primes, newprime(5)

number = new_prime(i); %finding permutations of the prime

y = num2str(number);

k = length(y);

for j = 1:k-1

y = circshift(y,1); %shifting mechanism by circshift function

z = str2num(y);

%z = [y y(1)]; %alternative shifting mechanism by str-num method

%z = str2num(z);

%z = z - str2num(y(1))*10^k;

%y = num2str(z);

if isprime(z) == 0 %checking if number is prime or not

new_prime(i) = 0; %indexing non-circular primes with zero

break %breaking out for next permutation of prime

end

%Final Stage - deleting all zeros

last_prime = new_prime(new_prime~=0);

output = length(last_prime);

toc

end