首页 团队成员,上杉九月的文章

文章简介

作者:上杉九月

排版及发布:上杉九月

前言

开一个讲解算法的栏目?我准备准备。

正文

普通判断法

代码实现

#include<bits/stdc++.h>
#define MAXN 10000000
using namespace std;
int pr[MAXN];
void Prime(int num)
{
    int temp;
    for(int i = 2; i <= num; i++)
    {
        temp = 0;
        for(int j = 2; j < sqrt(i); j++)
        {
            if(i % j == 0)
            {
                temp++;
            }
        }
        if(temp <= 2)
        {
            pr[i] = 1;
        }
    }
}
int main()
{
    int num;
    cin>>num;
    
    for(int i = 2; i <= num; i++)
    {
        if(pr[i] == 1)
        {
            cout<<i<<"\n";
        }
    }
    return 0;
}

埃拉托斯特尼筛法

定义

埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

图片演示

代码实现

#include<bits/stdc++.h>
#define MAXN 10000000
using namespace std;
int prime[MAXN];
void FindNum(int num)
{
    for(int i = 2; i <= sqrt(num); i++)
    {
        if(prime[i] == 0)
        {
            for(int j = i * 2; j <= num; j += i)
            {
                prime[j] = 1;
            }
        }
    }
}
int main()
{
    int num;
    cin>>num;
    FindNum(num);
    
    for(int i = 2; i < num; i++)
    {
        if(prime[i] == 0)
        {
            cout<<i<<" ";
        }
    }
    return 0;
} 

线性筛

原理

洛谷用户@学委的原理性证明

代码实现

#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
int prime[MAXN];
bool check[MAXN];
int temp;
void FindNum(int num)
{
    for(int i = 2; i <= num; i++)
    {
        if(check[i] == 0)
        {
            prime[++temp] = i;
        }
        for(int j = 1; j <= temp && i * prime[j] <= num; j++)
        {
            check[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                break;
             } 
        }
    }
}
int main()
{
    int num;
    cin>>num;
    FindNum(num);
    for(int i = 2; i <= temp; i++)
    {
        cout<<prime[i]<<"\n"; 
    }
    return 0;
}

about_me




文章评论

目录