The problem statement can be found here. In short, here's what the problem is about:
You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number to be psycho, its number of prime factors that occur even times should be greater than the number of prime factors that occur odd number of times. Else, it's ordinary.
My solution for this is as follows:
- First, I initialize the Sieve of Eratosthenes. This is the fastest method I know to get a list of prime numbers.
- Next, I loop over all the test cases and loop over all it's factors that are prime to increment the even and odd counter, to finally compare them and find the answer. For this I have to loop from 0 to half of the number.
This algorithm of mine is \$O(n)\$ for one input. Since the input size is of the order of \$10^7\$ and the number of inputs of the order of \$10^6\$ my algorithm takes time of the order of \$10^{13}\$. I need help with reducing this time.
#include <cstdio>
using namespace std;
bool primes[5000000];
void erastho()
{
for (int i = 0; i < 5000000; i++)
{
primes[i] = 1;
}
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i < 3164; i = i + 1)
{
if (primes[i])
{
int p = i*2;
while(p < 5000000)
{
primes[p] = 0;
p = p + i;
}
}
else continue;
}
}
int main()
{
erastho();
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
int hal = n/2;
int v, ev = 0, od = 0;
for (int i = 2; i <= hal; i++)
{
if((primes[i]) && (n%i == 0))
{
while (n%i == 0)
{
n = n/i;
v++;
}
if (v % 2 == 0) ev++;
else od++;
v = 0;
}
}
if (ev > od)
{
printf("%s \n","Psycho Number");
}
else
{
printf("%s \n", "Ordinary Number");
}
}
}
main()
loop rather than the the way of finding the primes. While the Atkin's Sieve looks a tad bit faster than the conventional one, I don't think that is what the problem demands. \$\endgroup\$ – Ranveer May 27 '14 at 7:27