私はオンライン審査システムから1つの問題を解決しようとしています。私にはうまくいく解決策がありますが、十分に効率的ではありません。ここに問題があります：
k個の方法のように製品n=a∙bで想像できる最小の数nはどれですか？製品a∙bおよびb∙aは、すべての数値が自然である（1≤k≤50）方法の1つです。
1つの数値kを入力します。1つの数値nを出力します。
私のコードは4つのテストに合格しませんでした。k = 31、37、47には遅すぎます。私はこの問題について2日間考えていましたが、改善は見られませんでした。これが私のコードです。何かアイデアがあれば共有してください。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int prime[10000];
long x,j,i,flag,k,length,p,checker,count,number;
int main()
{
prime[0]=2;
scanf("%ld",&k);
//I find prime numbers between 1 and 1000. 1000 can be changed, just for testing
for (i=3;i<=1000;i=i+2)
{
flag=0;
for (j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)
{
x++;
prime[x]=i;
}
}
length=x;
//this loop is too big I know, again for testing. I suspect, there must be a way to make some changes to this for loop
for (i=1;i<10000000000;i++)
{
number=i;
p=1;
for(x=0;x<=length;x++)
{
if(prime[x]>sqrt(i))
break;
count=0;
while(number%prime[x]==0)
{
number=number/prime[x];
count++;
}
p=p*(count+1);
//I find prime factors of numbers and their powers, then calculate number of divisors
}
//printf("%d\n",p);
//number of ways is just number of divisors/2 or floor (divisors/2)+1
if(p%2==0)
checker=p/2;
else
checker=floor(p/2)+1;
if(checker==k)
{
printf("%ld\n",i);
break;
}
}
return 0;
}