Psycho and ordinary numbers

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.