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