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 
using namespace std;

bool primes[5000000];

void erastho()
{
   for (int i = 0; i  od)
      {
         printf("%s \n","Psycho Number");
      }
      else
      {
         printf("%s \n", "Ordinary Number");
      }
   }
}

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. ;)

StackExchange Code Review Q#51805, answer score: 3