Untitled
unknown
c_cpp
3 years ago
839 B
6
Indexable
#include <stdio.h> #include<math.h> #include<stdbool.h> #include<string.h> bool c[463500]; long long int p[10000000]; long long int plen=0; void sieve() { int i,j; memset(c,0,sizeof(c)); c[0]=c[1]=1; for(i=2;i<=463500;i++) { if(c[i]==1) continue; p[plen]=i; plen++; for(j=i+i;j<=463500;j+=i) { c[j]=1; } } return; } bool isPrime(int n) { if(n<=463500) return(!c[n]); else { long long int q=(int)sqrt(n); long long int k; for(k=0;k<plen&&p[k]<=q;k++){ if(n%p[k]==0) return false; else continue; } return true; } } int main(){ sieve(); long long int t,n; /* for(int i=0;i<10;i++){ printf("%d ",p[i]); } printf("\n"); */ scanf("%lld",&t); while(t--){ scanf("%lld",&n); if(isPrime(n)) printf("True\n"); else printf("False\n"); } return 0; }
Editor is loading...