987654321的最大质因数那题，但是执行效率很低（改数字为134知编....

wkl

#include <stdio.h>
#include <math.h>
#define N 987654321
int main()
{
        int i,j,k=0,t=0;
        for(i=5;i<=N/2;i++)
    {
                for(j=2;j<=sqrt(i);j++)
                {
                        if(i%j==0)
                        {
                                t=1;
                                break;
                        }
                        else
                                t=0;
                }
        if(t==1)
                        continue;
                if(N%i==0)
                        k=i;
    }
    printf("The minimum prime factor is %d\n",k);
        return 0;
}

virfyf

这一题有另一种算法
[mw_shl_code=c,true]#include <stdio.h>
int main()
{
        int i,j,f,m=-1,n=987654321;
        i=2;
        while(i<n)
        {
                f=1;
                for(j=2;j*j<=i;j++)
                {
                        if(i%j==0)
                        {
                                f=0;
                                break;
                        }
                }
                if(f && n%i==0)
                {
                        n/=i;
                        m=i;
                }
                i++;
        }
    printf("The minimum prime factor is %d\n",m);
    return 0;
}[/mw_shl_code]

wkl

求大神修改之

virfyf

还有for(j=2;j<=sqrt(i);j++)这一句
建议改成for(j=2;j*j<=i;j++)
这样比前者的执行效率高多了
因为sqrt函数很耗时间

wkl

virfyf 发表于 2012-9-5 12:58
还有for(j=2;j

thank you!

kkk

纠正virfyf的一个错误：第6行while (i < n)应改为while (i <= n)。另可用system("pause")代替sleep(5000)

wiky315

virfyf 发表于 2012-9-5 10:20
这一题有另一种算法
[mw_shl_code=c,true]#include
int main()

求注解 .光看代码稍微有点迷糊.!

aa小菜鸟

virfyf 发表于 2012-9-5 10:20
这一题有另一种算法
[mw_shl_code=c,true]#include
int main()

俺不懂F的作用

小榛鼠

[mw_shl_code=c,true]#include <stdio.h>
int main()
{
    int i=0,j=0,f=0,m=0,n=64;
   
    for(i=2;i<=n;i++)     //i循环到n
    {
        f=1;
        for(j=2;j*j<=i; j++)//判断i是合数还是质数 （一个合数的最小质因数肯定小于等于他的平方根,n/p>=p,n>=p^2
        {
            if(i%j==0)    //如果i是合数
            {
                f=0;                //f=0
                break;    //退出当前循环
            }
        }
        if(f && n%i==0)  //如果f为1，确定i是质数，再由n%i判断i是否n的因数
        {
            n/=i;                //分解质因数的方法是用一个合数的最小质因数(i)去除这个合数(n)
            m=i;               
        }
        
    }
    printf("The minimum prime factor is %d\n",m);
    return 0;
}[/mw_shl_code]