快速求n的质因子

如何尽快地求出n的质因子呢？我们这里又涉及两个好的算法了!
第一个：用于每次只能求出一个数的质因子,适用于题目中给的n的个数不是很多，但是n又特别大的

#include<stdio.h>

int main()

{

   __int64 a[100],num,i,n;

   while(scanf("%I64d",&n)!=EOF)

   {

      num=0;

      for(i=2;i*i<=n;i++)

      {

          if(n%i==0)

          {

              a[num++]=i;

              while(n%i==0)

                 n=n/i;

          }

      }

      if(n>1)

         a[num++]=n;

      for(i=0;i<num;i++)

          printf("%I64d ",a[i]);

      printf("\n");

   }

   return 0;

}

第二个：一次求出1~n的所有数的质因子,适用于题目中给的n个数比较多的，但是n不是很大的。

#include<iostream>

#include<vector>

#include<algorithm>

#include<string.h>

using namespace std;

int visited[100010];

vector<int>a[100010];

void init()

{

    int i,j;

    for(i=0;i<100010;i++)

       a[i].clear();//vector的清空

    memset(visited,0,sizeof(visited));

    for(i=2;i<=100000;i++)

    {

        if(visited[i]==0)//i是素数这是可以保证的

        {

            a[i].push_back(i);

            for(j=i+i;j<=100000;j+=i)//筛选素数，其实这种方法没以前那种素数法快，但是这里用来求一个数的质因子就比较好了

            {

                visited[j]=1;

                a[j].push_back(i);

            }

        }

    }

}

int main()

{

    int i,j;

    init();

    for(i=0;i<=50;i++)

    {

        printf("%d:",i);

        for(j=0;j<a[i].size();j++)

            printf("%d ",a[i][j]);

        printf("\n");

    }

    return 0;

}

转载自：http://www.cnblogs.com/jiangjing/archive/2013/06/03/3115470.html

巴特西

快速求n的质因子(数论)

快速求n的质因子

最新文章

热门文章