/* Author : ~swim~ Date : 12-May-2018 Description: [ASSIGNMENT] Shortable Prime Numbers PART 1: Prime number is called Shortable if it can be consiquently reduced by 1 digit (until sigle digit Prime rests) from any chosen in advance side and resulting number is also Prime. Shortable Prime can be called Left/Right/Full Shortable Prime if it can be reduced from left/right/both sides. For example: 13 -> 3 => 13 is Left Shortable Prime 31 -> 3 => 31 is Right Shortable Prime 3797 -> 797 -> 97 -> 7 and 3797 -> 379 -> 37 -> 3 => 3797 is Full Shortable Prime TASK 1: Write a code which checks if input number is Shortable Prime. Print out not only True or False but specify what kind of Shortable Prime it is: Left, Right or Full. TASK 2: Write a code which finds all Shortable Prime in a given range [A,B] and print them out grouped by Left, Right and Full Shortable Primes. EXTRA TASK: For tasks 1 and 2 print out not only numbers itself, but also its reducing process like it is shown in the example or any other way you like. :-) CLARIFICATION NOTES: - Single digit Primes are not Shortable Primes. - If number is Full Shortable Prime there is no need to print it also in lists of Left and Right Shortable Primes. - Numbers that contain '0' as a digit can be Left Shortable Primes according to a general rule. Example: 5003. It is Prime and 3 is Prime as well. However, it is not Right Shortable Prime, because 500 and 50 are not Prime numbers. Input: Enter a number and press submit */ #include #include using namespace std; using ll=long long; // standard algo to determine if no is prime or not bool isPrime(ll n) { if(n < 2) return false; if(2 == n || n == 3 || n == 5 || n == 7 ) return true; // filter out even if(!(n&1)) return false; for(ll i=3,sq=sqrt(n)+1; i<=sq; i+=2) if(!(n%i)) return false; return true; } // check if prime no is right shortable prime. To check it successively remove rightmost digit and check if the remaining number is prime. bool isRightShortableP(ll n) { // one digit no is not shortable if(n < 10) return false; bool isRSP{true}; do { isRSP = isPrime(n); n /= 10; } while(n > 0 && isRSP); return isRSP; } // custom power function ll P(int i) { ll n=10; return i ? n*P(i -1) : 1; } // check if prime no is left shortable prime. To check it successively remove leftmost digit and check if the remaining number is prime. bool isLeftShortableP(ll n) { // one digit no is not shortable if(n < 10) return false; bool isLSP = isPrime(n); if(isLSP) { int d = floor(log10(n))+1; do { ll num = n%P(--d); isLSP = isPrime(num); } while(d>1 && isLSP); } return isLSP; } bool isFullShortableP(ll n) { return isLeftShortableP(n) && isRightShortableP(n); } // it will print the leading 0 void PrintLeftPath(ll num) { string str = to_string(num); cout << str << " => "; for(int i=1,sz=str.size()-1; i "; cout << *--str.end() << "\n\n"; } void PrintRightPath(ll num) { cout << num << " => "; while(num > 100) { num /= 10; cout << num << " => "; } num /= 10; cout << num << "\n\n"; } int main() { ll num; cin >> num; if(num < 0) { cout << "error, enter a positive number"; return -1; } bool isLSP = isLeftShortableP(num); if(isLSP) { cout << boolalpha << num << " is Left Shortable Prime\n"; PrintLeftPath(num); } bool isRSP = isRightShortableP(num); if(isRSP) { cout << boolalpha << num << " is Right Shortable Prime\n"; PrintRightPath(num); } if(isLSP && isRSP) { cout << boolalpha << num << " is also Full Sortable" " Prime\n"; } if(!isLSP && !isRSP) { cout << num << " is not Shortable" " Prime\n"; } }

Shortable_Primes.cpp