SPOJ PAGAIN - Prime Again Solution
help:don't sumit c++14(clang8.0),other c++ laguage this is accepted
Solution in C++:
////**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd Batch
///Islamic University,Bangladesh
#include<iostream>
#include<vector>
#define M 1000010
#define ll long long
using namespace std;
bool marked[M];
vector<ll >v;
void sieve()
{
for(ll i=3; i*i<=M; i+=2)
{
if(marked[i]==false)
{
for(ll j=i*i; j<=M; j+=2*i)
{
marked[j]=true;
}
}
}
v.push_back(2);
for(ll i=3; i<=M; i=i+2)
{
if(marked[i]==false)
{
v.push_back(i);
}
}
}
void value(ll n)
{
for(ll i=0; v[i]*v[i]<=n; i++)
{
if(n%v[i]==0)
{
i=-1;
n--;
}
}
cout<<n<<endl;
}
int main()
{
sieve();
ll n,a,f,i,t;
cin>>t;
while(t--)
{
cin>>n;
value(n-1);
}
}
Solution in C++:
////**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd Batch
///Islamic University,Bangladesh
#include<iostream>
#include<vector>
#define M 1000010
#define ll long long
using namespace std;
bool marked[M];
vector<ll >v;
void sieve()
{
for(ll i=3; i*i<=M; i+=2)
{
if(marked[i]==false)
{
for(ll j=i*i; j<=M; j+=2*i)
{
marked[j]=true;
}
}
}
v.push_back(2);
for(ll i=3; i<=M; i=i+2)
{
if(marked[i]==false)
{
v.push_back(i);
}
}
}
void value(ll n)
{
for(ll i=0; v[i]*v[i]<=n; i++)
{
if(n%v[i]==0)
{
i=-1;
n--;
}
}
cout<<n<<endl;
}
int main()
{
sieve();
ll n,a,f,i,t;
cin>>t;
while(t--)
{
cin>>n;
value(n-1);
}
}
No comments