#include <iostream> #include <sstream> #include <ctime> #include <stdlib.h> using namespace std; long long a,d=10; long long pot2[46]; long long power_modulo_fast(long long a, long long b, long long m){ long long i; long long result = 1; long long x = a%m; for(i=1;i<=b;i<<=1){ x%=m; if((b&i)!=0){ result*=x; result%=m; } x*=x; } return result; } bool pierwsza(long long n){ long long s=0; long long s2=1; long long a,d,prime; srand(time(NULL)); if(n<4) return 1; if(!n%2) return 0; while(!(s2&(n-1))){ s+=1; s2<<=1; } d=n/s2; for(int i=0; i<20; i++){ a=1+(long long)((n-1)*rand()/(RAND_MAX+1.0)); if(power_modulo_fast(a,d,n)!=1){ prime=0; for(int r=0; r<=s-1; r++){ if(power_modulo_fast(a,pot2[r]*d,n)==n-1){ prime=1; break; } } if(!prime) return 0; } } return 1; } bool sprawdz(long long x){ ostringstream str; str << x; for(int i=1; i<str.str().size(); i++){ if((x%d)>=(d/10)){ if(pierwsza(x%d) && pierwsza(x/d)) return true; d*=10; } } return false; } int main() { ios_base::sync_with_stdio(0); pot2[0]=1; for(int i=1; i<46; i++){ pot2[i]=2*pot2[i-1]; } cin >> a; if(sprawdz(a)) cout << "TAK"; else cout << "NIE"; return 0; }
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <iostream> #include <sstream> #include <ctime> #include <stdlib.h> using namespace std; long long a,d=10; long long pot2[46]; long long power_modulo_fast(long long a, long long b, long long m){ long long i; long long result = 1; long long x = a%m; for(i=1;i<=b;i<<=1){ x%=m; if((b&i)!=0){ result*=x; result%=m; } x*=x; } return result; } bool pierwsza(long long n){ long long s=0; long long s2=1; long long a,d,prime; srand(time(NULL)); if(n<4) return 1; if(!n%2) return 0; while(!(s2&(n-1))){ s+=1; s2<<=1; } d=n/s2; for(int i=0; i<20; i++){ a=1+(long long)((n-1)*rand()/(RAND_MAX+1.0)); if(power_modulo_fast(a,d,n)!=1){ prime=0; for(int r=0; r<=s-1; r++){ if(power_modulo_fast(a,pot2[r]*d,n)==n-1){ prime=1; break; } } if(!prime) return 0; } } return 1; } bool sprawdz(long long x){ ostringstream str; str << x; for(int i=1; i<str.str().size(); i++){ if((x%d)>=(d/10)){ if(pierwsza(x%d) && pierwsza(x/d)) return true; d*=10; } } return false; } int main() { ios_base::sync_with_stdio(0); pot2[0]=1; for(int i=1; i<46; i++){ pot2[i]=2*pot2[i-1]; } cin >> a; if(sprawdz(a)) cout << "TAK"; else cout << "NIE"; return 0; } |