素数筛选和合数分解

清疚 2022-07-17 00:18 189阅读 0赞

具体代码实现如下：

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int MAXN=100000;///MAXN的大小与题目规模有关
    int prime[MAXN+1];
    void getPrime()
    {
        memset(prime,0,sizeof(prime));
        for(int i=2;i<=MAXN;i++)
        {
            if(!prime[i])
                prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
            {
                prime[prime[j]*i]=1;
                if(i%prime[j]==0)
                    break;
            }
        }
    }
    long long factor[100][2];
    int fatCnt;
    int getFactors(long long x)
    {
        fatCnt=0;
        long long tmp=x;
        for(int i=1;prime[i]<=tmp/prime[i];i++)
        {
            factor[fatCnt][1]=0;
            if(tmp%prime[i]==0)
            {
                factor[fatCnt][0]=prime[i];
                while(tmp%prime[i]==0)
                {
                    factor[fatCnt][1]++;
                    tmp/=prime[i];
                }
                fatCnt++;
            }
        }
        if(tmp!=1)
        {
            factor[fatCnt][0]=tmp;
            factor[fatCnt++][1]=1;
        }
        return fatCnt;
    }
    
    int main()
    {
        long long n;
        getPrime();
        cin>>n;
        int num=getFactors(n);
        for(int i=0;i<num;i++)
        {
            cout<<factor[i][0]<<"   "<<factor[i][1]<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关筛选100以内的素数

//筛选100以内的素数 include<stdio.h> include<math.h> int main() { int

待我称王封你为后i/ 2023年07月17日 11:29/ 0 赞/ 195 阅读

相关质数/素数 - 合数

质数/素数 - 合数 prime [praɪm]：n. 盛年，年富力强的时期，鼎盛时期 adj. 主要的，首要的，基本的，优质的 v. 事先指点，使 (某人) 做

本是古典何须时尚/ 2023年01月11日 03:56/ 0 赞/ 226 阅读

相关埃氏筛选与线性筛选求素数

//埃氏筛选法复杂度O(nlognlogn) include<bitset> include<map> include<vector>

红太狼/ 2022年08月03日 14:51/ 0 赞/ 240 阅读

相关素数筛选和合数分解

具体代码实现如下： include <iostream> include <cstring> using namespace std;

清疚/ 2022年07月17日 00:18/ 0 赞/ 190 阅读

相关求素数（普通+筛选）

一般求解n以内素数的算法。时间复杂度是o(n\sqrt(n)),当n较小时可以用。代码： ![Center][] 当n较大时，一般选用埃氏筛选法，时间复杂度o(n

逃离我推掉我的手/ 2022年06月11日 08:23/ 0 赞/ 254 阅读

相关线性筛选素数

/ @author liu / public class Main{ public static void main(String[] args) { final

男娘i/ 2022年06月02日 03:06/ 0 赞/ 202 阅读

相关算法：素数筛选

include <stdio.h> include <stdlib.h> int main(void) { //这个是输出1000以内的

Love The Way You Lie/ 2022年03月20日 15:58/ 0 赞/ 286 阅读

相关质数（素数）和合数

质数质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。否则称为合数。最小的质数是2，也是唯一的一个既是偶数又是质数的数。也就是说

电玩女神/ 2022年03月11日 09:50/ 0 赞/ 235 阅读

相关筛选法求素数

int vis[1000]; //记录标记 int p[1000]; //存素数 int main() { int n,i

系统管理员/ 2022年03月10日 07:45/ 0 赞/ 335 阅读

相关素数筛选高效算法

用普通的筛法，1000 0000 的数，需要用时1600ms左右。 include <stdio.h> include <string.h> incl

妖狐艹你老母/ 2021年11月02日 14:32/ 0 赞/ 364 阅读