/* 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 #include #include #include #define Print_Primes 0 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; } // custom power function ll P(int i) { ll n=10; return i ? n*P(i -1) : 1; } // 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) { bool isRSP{true}; n /= 10; do { isRSP = isPrime(n); n /= 10; } while(n > 0 && isRSP); return isRSP; } // 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 bool isLSP{true}; int d = floor(log10(n))+1; do { ll num = n%P(--d); isLSP = isPrime(num); } while(d>1 && isLSP); return isLSP; } // Standard Sieve prime generator //vector auto Gen_primes(ll lb, ll ub) { vector primes{2}; char *sieve = new char[(ub>>3)+1]; // populate sieve with 1 memset(sieve, 0xFF, ((ub>>3)+1) * sizeof(char)); for(ll x = 3; x <= ub; x+=2) if(sieve[x>>3] & (0x01<< (x&7))) { primes.emplace_back(x); // set all multiples to zero for(ll j = 3*x; j<=ub; j+=x) sieve[j>>3] &= ~(0x01 <<(j&7)); } delete[] sieve; sieve = nullptr; return primes; } auto Print =[](auto const& Primes) { if(Primes.size() > 0) { for(auto e: Primes) cout << e << " "; cout << endl << endl; } }; void checkShortable(auto const& primes, ll range) { vector leftShortableP; vector rightShortableP; vector fullShortableP; bool isLSP{}; //leftshortable prime bool isRSP{};//rightshortable prime for(auto n:primes) { isLSP=isLeftShortableP(n); isRSP=isRightShortableP(n); if(isLSP && isRSP) fullShortableP.emplace_back(n); else if(isRSP) rightShortableP.emplace_back(n); else if(isLSP) leftShortableP.emplace_back(n); } cout << "In the range (0," << range << "),\n" << "The number of" << " leftShortablePrimes = \n" << leftShortableP.size() << "\n"; Print(leftShortableP); cout << "The number of rightShortablePrimes = \n" << rightShortableP.size() << "\n"; Print(rightShortableP); cout << "The number of FullShortablePrimes = \n" << fullShortableP.size() << "\n"; Print(fullShortableP); } int main() { ll range; cin >> range; if(range < 0) { cout << "error, enter a positive" " number\n"; return -1; } if(range <= 10) { cout << "There are no left, right or full shortable primes in the range"; } // generate prime numbers vector primes = Gen_primes(2,range); cout << primes.size(); #if Print_Primes for(auto e:primes) cout << e << " "; cout << endl; #endif // check if prime is left, right or // full shortable checkShortable(primes, range); }

Shortable_primes_range(Task 2).cpp