CODEWITHSUNDEEP
c++long-integermodulofactorization
naman
naman

Reputation: 85

how to check divisibility of a very long number in c++?

How to check divisibility of a very long number in c++? i have to check if (3*n*n+3*n-1) is divisible by 2 , 3 and 5 and n can be upto 10^10 so long long int is also doubtful to work although i have tried doing this:

unsigned long long int gg4,l;
gg4=(3*n*n+3*n-1);
if(gg4%3==0){
    gg4=gg4/3;
}
if(gg4%2==0){
    gg4=gg4/2;
}
if(gg4%5==0){
    gg4=gg4/2;
}

But i guess this wont work because of the range of n so please help! :)

after this i also need to divide (3*n*n+3*n-1) by that factor so please help!

Upvotes: 2

Views: 457

Answers (1)

user555045
user555045

Reputation: 64913

To expand on my comment, there are two cases when (3*n*n+3*n-1) % 5 == 0, namely

  • n = 5 * m + 1
  • n = 5 * m + 3

For m an integer.

So in fact you don't need to calculate a long anything, you can work directly with n, and never even calculate 3 * n * n + 3 * n - 1 in the first place.

Just check:

n % 5 == 1 || n % 5 == 3

Upvotes: 3

Related Questions