c++ - Why is Wrong answer Uva : Factovisors -

for problem 10139 - factovisors on uva online judge, 2 numbers n , m given, , need check whether m divides n!.

i use algorithm:

1. generate primes till const number

2. take m , primes factor

3. for each prime in m's factors, calculate getpower function n , compare them

i test different cases give me wrong answer, suggestion?

here's code:

bool factovisor (int n, int m) {  /* special cases */       if(n==0 && m!=1 )          return false;     else if(n==0&&m==1)          return true;     else if(m==0)          return false;     else if(m==n||m==1)          return true;     else if (n >= m)         return true;     else {          vector <factores> factores_in_m;          int index = 0;         int k=m; /* first generate primes in primes vector */          (int = 0; < primes.size(); i++) {             if (primes[i] > k) {                 break;              } else { /* factores struct contain prime , count*/                  factores f = {primes[i], 0};                 while (k % primes[i] == 0) {                     f.count += 1;                     k = k / primes[i];                 }                  if (f.count) {                     factores_in_m.push_back(f);                 }             }         }          if (k > 1) {              if (n < k) {                 return false;             } else {                 factores f;                 f.prime= k;                 f.count =1;                 factores_in_m.push_back(f);             }         }          (int = 0; < factores_in_m.size(); i++) {             if (factores_in_m[i].count - get_powers(n, factores_in_m[i].prime) > 0) {                 return false;             }         }         return true;     } }  int get_powers (int n, int p) {     int result = 0, power = p;     while (power <= n) {          result += n / power;         power =power* p;     }     return result; }  bool isprime (int n) {     (int = 2; < n; i++) {         if (n % == 0) {             return false;         }     }     return true; }  void get_prime () {     (int = 2; < maxn0; i++) {         if (isprime(i)) {             primes.push_back(i);         }     } } 

maybe prime generation faulty, get_powers implementation susceptible int overflow.

int get_powers (int n, int p) {     int result = 0, power = p;     while (power <= n) {          result += n / power;         power =power* p;     }     return result; } 

if int is, is, 32-bit wide type, primes larger 46341 computation power = power * p; overflows first time done. can lead wrong results, example

get_powers(10000000, 131071) 

returns 52 if overflow behaviour wraparound modulo 2³², correct result 76. now, since m smaller 2³¹, particular 1 wouldn't hurt, since m cannot divisible 131071². under wraparound behaviour,

get_powers(1000000, 699733) = -2192 

is negative, n = 1000000 , m = 2*699733 example, wrongly conclude n! isn't divisible m.

to avoid possible overflow, divide p,

int get_powers(int n, int p) {     int result = 0;     n /= p;     {         result += n;         n /= p;     }while(n > 0);     return result; } 

---

from comments:

i edited add functions primes till constant number "maxn0" – userg 2 hours ago

what value have chosen maxn0? – daniel fischer 2 hours ago

maxn0 = 10000

that value small.

with primes 10000, guaranteed correctly factorise numbers not exceeding 10⁸ (well, since next prime 10007, numbers smaller 10007² = 100140049), limit given 2³¹, larger.

whenever number m given 2 (not distinct) prime factors larger 10000, not correctly factorise that, , lead wrong answer.

you need primes ≤ √(2³¹-1), primes < 46340 obtain correct factorisation of admissible m.