0

I am working on my algorithm for solving problems related to divisors.

I have created a program that

1. If first number of input is 1

Given integer n<10^18, I found the largest number x with largest number of divisors k.

2.If first number of input is 2

Given integer k<2*10^5

I need to find the largest number with k divisors(which can be found from question1)

Then I need to find a smallest number with at least k divisors

here is my code

#include <algorithm> 
#include <stdio.h>
#include <limits.h>
using namespace std;
unsigned long long n, res,i,x,y,z,w;
int a,p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};

unsigned long long mul(unsigned long long a, unsigned long long b){
unsigned long long res = 0;

while (b){
    if (b & 1LL) res = (res + a);
    if (res >= n) return 0;
    a = (a << 1LL);
    b >>= 1LL;
    }

    return res;
}

void backtrack(int i, int lim, unsigned long long val, unsigned long long r)
{
//finds the largest number of divisor k for some number smaller than input
if (r > res) res = r;
if (i == p) return;

int d;
unsigned long long x = val;

for (d = 1; d <= lim; d++){
    x = mul(x, primes[i]);
    if (x == 0) return;
    backtrack(i + 1, d, x, r * (d + 1));
    }
}



void dfs(int pos,unsigned long long ans,unsigned long long sum,int pre)
{
//finds the smallest number given number of divisors k
    if(sum>x)return;
    if(sum==x)
    z=min(ans,z);
    for(int i=1;i<=pre;i++)
    {
        if(1e18/ans<primes[pos])break;
        dfs(pos+1,ans*=primes[pos],sum*(i+1),i);
    }
}


int main(){
/* Tested for n <= 10^18 */

p = sizeof(primes) / sizeof(int);

scanf("%d %llu", &a ,&n);
if(a ==1){
//case 1
    res = 0;
    backtrack(0, 100, 1, 1);
    x=res;
    z= 1e18;
    dfs(0,1,1,63);
    printf("%llu %llu\n", res,z);
    }
else{
//case2 not implemented yet
    res = 0;
    x=n;
    z= 1e18;
    dfs(0,1,1,63);


    }
    return 0;
}

I need to find the final section: find a smallest number with at least k divisors. Any advice?

Daniel
  • 15
  • 5
  • 1
    What is the issue? It is unclear with the information you provided. – Amit Kumar Jun 08 '17 at 08:55
  • See https://stackoverflow.com/questions/31270226/how-to-calculate-smallest-number-with-certain-number-of-divisors/31271590 – Miljen Mikic Jun 08 '17 at 11:58
  • @MiljenMikic I have already found implementation for the problem you have posted. I have found the smallest number with exactly k divisors. Now I need to find smallest number with at least k divisors. For example, 16 has 5 divisors. But 12 has 6 divisors. Thus, 12 is the smallest number with at least 5 divisors. – Daniel Jun 08 '17 at 13:30

0 Answers0