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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
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 |