Psycho and ordinary numbers

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");
}
}
}

• hint : see that you have a collection/array of only primes in stead of a big array with booleans. Iterating over all booleans takes longer then over a collection/array that contains only primes. May 27 '14 at 7:22
• en.wikipedia.org/wiki/… this might be helpful to you. there is mentioned a "Sieve of Atkin" that's faster than the good old sieve of eratosthenes... Also are primes themselves psycho or not? (they have a single prime factor, so I figured, yes..) May 27 '14 at 7:24
• @chillworld so you mean to say that in the function where I initialize the eratosthenes sieve, I should return a vector(?) of primes instead of a boolean array? Not a bad idea in fact. That way I could iterate over the prime numbers only and reduce the loop time by approximately 1/10th. May 27 '14 at 7:25
• @Vogel612 I think I need to optimize my 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. May 27 '14 at 7:27
• When looping over the numbers prime factors, you only need to go up to sqrt(N), not N/2. Each factor <= sqrt(N) will pair with exactly one factor >= sqrt(N). May 27 '14 at 7:41

Do not use namespace std:

There is multiple reviews on that here on this site already, so I'll just sum it up shortly:

using namespace std pollutes global namespace and leads to possible conflicts with other functions. For more information you can read this stackoverflow post on the matter.

Naming:

Simply because of your variable names I found it hard to understand what exactly you were doing. Characters are not costly. Anymore that is, but you should really write out what your variables are supposed to do:

od --> oddFactorOccurence
ev --> evenFactorOccurence
v --> currentFactorCounter
n --> number
t --> countOfNumbers
hal --> half / evalThreshold
erastho... no. just. NO. ;)

• About the naming thing, sorry for that. Actually in many competitions, least characters of code get you more points, so I'm into a habit of coding like that. I'll keep that in mind while posting the next time. May 27 '14 at 7:55

For your list of primes you might want to consider something more optimized for that:

vector<int> PrimeList()
{
int sieveBound = (int)(PRIME_LIMIT - 1) / 2;
int upperSqrt = ((int)sqrt(PRIME_LIMIT) - 1) / 2;
vector<int> numbers(PRIME_LIMIT);
bool PrimeBits[PRIME_LIMIT] = {false};
int numbersindex = 0;
numbers[numbersindex++] = 2;
for(int i = 1; i <= upperSqrt; i++)
{
if(!PrimeBits[i])
{
int increment = 2 * i + 1;
for(int j = i * 2 * (i + 1); j <= sieveBound; j += increment)
{
PrimeBits[j] = true;
}
numbers[numbersindex++] = increment;
}
}
for(int i = upperSqrt; i <= sieveBound; i++)
{
if(!PrimeBits[i])
numbers[numbersindex++] = 2 * i + 1;
}
numbers.resize(numbersindex);
return numbers;
}


This not only builds the sieve faster, by using an offset algorithm, but eliminates part of the loop by building the list while building the sieve. It uses a bool array to hold the sieve and a vector, pre-allocated then resized, to hold the list.

Your limit was a little small to get accurate timing, but by increasing it to 1000000, this code ran a good 70% faster.

It finally worked after a few optimizations. Here's the final code:

#include <cstdio>
#include <math.h>
#include <vector>

bool isPrime[3164];

void eratosthenesSieve()
{
for (int i = 0; i < 3164; i++)
{
isPrime[i] = 1;
}
isPrime[0] = 0;
isPrime[1] = 0;
for (int i = 2; i < 3164; i = i + 1)
{
if (isPrime[i])
{
int tempVariable = i*2;
while(tempVariable < 3164)
{
isPrime[tempVariable] = 0;
tempVariable = tempVariable + i;
}
}
else continue;
}
}

int main()
{
erathosthenesSieve();
std::vector <int> primesList;
for (int i = 0; i < 3164; i++)
{
if (isPrime[i])
{
primesList.push_back(i);
}
}
int numberOfPrimes = primesList.size();
int testCases;
scanf("%d", &testCases);
while(testCases--)
{
int number;
scanf("%d", &number);
int tempCounter, evenCounter = 0, oddCounter = 0;
for (int i = 0; i < numberOfPrimes; i++)
{
if(number % primesList[i] == 0)
{
while (number % primesList[i] == 0)
{
number = number/primesList[i];
tempCounter++;
}
if (tempCounter % 2 == 0) evenCounter++;
else oddCounter++;
tempCounter = 0;
}
}
if (number > 1) oddCounter++;
if (evenCounter > oddCounter)
{
printf("%s \n","Psycho Number");
}
else
{
printf("%s \n", "Ordinary Number");
}
}
}


The optimizations:

• There can be at max 1 factor that would be greater than sqrt(N). And that would be the number left after successive division by its prime factors until sqrt(N). So the loop goes on until sqrt(max possible input = 3164).
• Owing to the above observation, the number of primes need to be found out are reduced.
• Lastly, instead of using a boolean array, I made an array of primes, further reducing the number of iterations.
• You might have waited for other reviews, they would definitely have some other stuff to say. How about you just fix that naming and namespace std thing and post a follow-up question? May 27 '14 at 12:37
• Actually, it was more of an algorithmic issue. Jerry Coffin's comment did it all. May 27 '14 at 12:45