/* Author : ~swim~ Date : 27-Apr-2018 Description: [ASSIGNMENT] Cyclic Prime Numbers Prime Number is considered to be a Cyclic Prime Number if all other numbers obtained by cyclic permutation of its digits are also Primes. For example: 197 -> 971 -> 719 P.S. Let's consider single digit Primes also as Cyclic Primes. TASK 1: Check if given number N is a Cyclic Prime Numbers. Input: 31 Output: True TASK 2: For given values A and B print all Cyclic Prime Numbers grouped by related numbers those all cyclic permutations are in a range from A to B. Input: 100 999 Output: ...find it... :-) Input: Enter a no to check for cyclic prime then space then lower bound then space then upper bound and press submit. If upper bound is not specidied it will be taken as zero and the program will exit with error message. Note: 1. Comprehensive input error checking not done 2. To consider memoization - when searching the range consider a number like 113. To check if it is cyclic prime you will also need to check 131 and 311 for prime. Then when the number 131 comes you need to check 113 and 311 but 113 has already been considered so checking 113 again for prime is recalculation. So whether memoization will improve performance i haven't given enough thought on it, although it seems so. */ #include #include #include #include #include using namespace std; using ull = unsigned long long; //Simple trial division test to check //if the number is prime or not //Return value: true if no. is prime, //false otherwise bool is_prime(ull num) { if(num < 2) { return false; } if(2 == num) { return true; } if(!(num&1)) { return false; } for(ull lb=3, ub=sqrt(num)+1; lb <= ub; lb+=2) { if(!(num % lb)) return false; } return true; } // end is_prime // check if a number is a cyclic // prime or not bool is_cyclic_prime(ull num, ull lb=0, ull ub=numeric_limits::max()) { // 1. check if number is prime // 2. if no return false // 3. if yes, then rotate the number // and check if the number is // prime. // 4. if any number fails prime // check return false if(is_prime(num)) { string nstr = to_string(num); for(int i=0, sz=nstr.size()-1; in || n>ub) return false; } // end for return true; }// end if(is_prime(num)) return false; }// bool is_cyclic_prime // finds all cyclic primes in the // range void find_cyclic_primes(auto&& plist, auto lb, auto ub) { if(lb<=2 && ub>=2) { plist.emplace_back(2); lb = 3; } if(!(lb&1)) lb++; for(ull i{lb}; i<=ub; i+=2) { if(is_cyclic_prime(i,lb,ub)) plist.emplace_back(i); } }// end find_cyclic_primes auto main()->int { // num to chk for cyclic prime ull cycp{0}; ull lb{0},// lower bound ub{0};// upper bound cin >> cycp >> lb >> ub; if(lb > ub) { cout << "error, upper bound cannot be less than lower bound!\n"; return -1; } cout << "is " << cycp << " cyclic prime number? : " << boolalpha << is_cyclic_prime(cycp) << "\n\n"; // find the cyclic primes in the // range vector v_cyc_p; find_cyclic_primes(v_cyc_p,lb,ub); if(v_cyc_p.size()) { cout << "cyclic primes in the range[" << lb << "," << ub << "]\n" << "are: "; for(auto e:v_cyc_p) cout << e << " "; cout << "\n"; }// end if(v_cyc_p.size()) else { cout << "no cyclic primes found in" " the\n" << "range [" << lb << "," << ub << "]\n"; } }

[Assignment] Circular_prime.cpp