Find an element in a matrix M*M of numbers which have exactly 3 divisors in given time?-CodePudding

This was a task given on a coding competition a few months ago, and its still bugging me now. I did solve it, but my code did not give the result in required time for 3 test samples, likely due to the very large numbers they used. The thing is, looking at my code i see no obvious improvements that would reduce the time further.

The input has 3 numbers: the side length of the matrix, row and column of the required number. For a matrix size 3, it would look like:

4   9   16
121 49  25
169 289 361

A number that has 3 divisors can only be a squared prime number, so my solution was to generate primes until the needed position.

#include<iostream>
bool prime(long long a)
{
    //if(a%2==0) 
    //  return false; //no numbers passed will be even
    for(long long i=3;i*i<=a;i =2)
        if(a%i==0) 
            return false;
    return true;
}
int main()
{
    int side, row, col, elem, count=1;
    long long num=1; 
    std::cin >> side >> row >> col;
    if(row==1 && col==1)
    {
        std::cout << '4';
        return 0;
    }
    elem=(row-1)*side col (row%2==0)*(side-2*col 1);//gets required position in matrix
    while(count<elem)
    {
        num =2;
        if(prime(num)) 
            count  ;
    }
    std::cout << num*num;
}

CodePudding user response：

Rather than this:

while(count<elem)
{
    num =2;
    if(prime(num)) 
        count  ;
}

This:

vector<long long> primes;
primes.push_back(2);

while (count < elem)
{
    num  = 2;
    if (prime(num, primes)) {
       primes.push_back(num);
       count  ;
    }
}

Where your prime function is modified to only test divisibility against previously found prime numbers:

bool prime(long long num, const vector<long long>& primes)
{
   for (auto p : primes)
   {
       if (num % p == 0)
       {
          return false;
       }
   }
   return true;
}

The above should speed things up significantly. There's also the sieve of eros thing. But the above should be sufficient for most leet coding challenge sites.

CodePudding user response：

A bare-bones implementation of Sieve of Eratosthenes, you could try with this:

bool is_prime(size_t p, std::vector<bool>& primes) {
  if (!primes[p]) return false;
  for (auto i = p * p; i < primes.size(); i  = p) {
    primes[i] = false;
  }
  return true;
}

void init_primes(std::vector<bool>& primes, size_t N) {
  primes = std::vector(N, true);
  primes[0] = false;
  primes[1] = false;
  primes[2] = true;
}

int main() {
  std::vector<bool> p;
  init_primes(p, 1000); // <- insert some large enough number here
  ...
}