的确是我理解错了,这样~

题目意思就是说满足条件的n1 n2都是由不重复的质因子组成的~

可以枚举所有由2 3 5 7 11 13 17 19 21 23这些不重复因子组成的所有数,然后找个绝对值最少的~

算法上 找质因数的方法可以优化一下

int foo(int n)
{
    for(int i = 2; i<=n; ++i)
    {
        if(n%i == 0)
            n/=i;
        if(n%i == 0)
            return 0;
    }
    return 1;
}

这样试试看

枚举在这里不好用
比如一个数字是 2*997
要枚举2的20多次方次 才能找到

对哦,枚举的确不好用,那先按你的方法试试~

或者可以试试打一个质数表~
用质数表逐个逐个除以该数效率也许会高一些~

要很大的质数表
一个10^18的开根

当然如果可以打表的话直接看看质数的平方能不能整除就可以了,所以打表求出10^9开平方范围内的所有质数就可以了

看过10^5范围内共有9592个质数,这题搜索最大范围是相邻两个质数的距离,搜过10^9范围内的相邻两个质数的最大距离是220,就算运算9592*220次怎么也不会超时吧~

欧拉筛求素数可以这样~

#include<stdio.h>

#define MAX 100
char IsPrime[MAX+1]={0};
int prim[MAX+1]={0};

int main()
{
    int i=0;
    int j=0;
    int num=0;

    for (i=2;i<=MAX;++i)
    {
        if (!IsPrime[i])
            prim[num++]=i;

        for (j=0;j<num&&i*prim[j]<=MAX;++j)
        {
            IsPrime[i*prim[j]]=1;

            if (i%prim[j]==0)
                break;
        }
    }

    for (i=0;i<num;++i)
        printf("%-4d",prim[i]);

    puts("");

    return 0;
}

[此贴子已经被作者于2018-5-19 04:34编辑过]

目前能想到的方法也是打表，可是打10亿范围内的素数表也是很费时的，我电脑花费16秒，应该超时了吧。

用质数表的确会更有效率
但这个质数表要硬编码到代码里面
如果是运行时计算那就没必要了
函数里面的循环是2到n
求质数的循环也是2到n
等于没有提升

事实上打表求区间范围会更加有优势(当然,说了等于没有说)
求单个数当然没有必要打表~
但线性筛求质数很明显是线性的,多于1个数的时候第二个数开始就可以用到表了~

其实17楼的说明还是忽略了一个问题,就是建表的时间,找10^5以内的质数遍历10^5次就可以了,弄得我重新看了一遍~

PS:然后我重新理解你所说的,一句话就是:用表求区间段素数可以在线性时间复杂度里面完成,上面就是个例子~

[此贴子已经被作者于2018-5-19 10:42编辑过]