Mister-小方


私信TA

用户名:1104986125

访问量:124745

签 名:

如此英俊为哪般

等  级
排  名 6
经  验 20444
参赛次数 1
文章发表 68
年  龄 19
在职情况 学生
学  校 大连交通大学
专  业 车辆工程

  自我简介:

TA的其他文章

解题思路:

明确一个条件,任何合数都能表示成一系列素数的积。

然后利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次。

所以为线性时间

参考代码:

#include<stdio.h>
int primes(int n);    
//其中primes()函数是用来排素数的函数
int prime[100000]={0};                        
//用来存储素数的数组,初始化全部为0
int p[100000]={0};                               
//用来间接验算是不是素数的数组,初始化全部为0
int main()
{
    int number,i,size;         
//其中number为用户输入的数,size为prime()传回来的在0~number以内有多少个素数
    scanf("%d",&number);
    size=primes(number);           
//传回多少个素数
    for(i=0;i<size;i++)
    {
        printf("%d\n",prime[i]);    
//输出
    }
    return 0;
}
int primes(int n)                    
{
    int top=0,i,j;                         
//定义top为prime[]中已有的素数个数
    for(i=2;i<=n;i++)
    {
        if(!p[i])                             
//判断p[i]有没有被修改过,如果没有被修改过,就还是0,
// 则对应此时的i为素数,否则就是1,将可以判断其肯定不是素数.
    {
        prime[top++]=i;               
        //输入素数
    }
    for(j=0;j<top&&i*prime[j]<=n;j++)
    {
        p[i*prime[j]]=1; 
//这个是欧拉筛选的精髓,当前的值与前面已经出现的素数相乘,其合数肯定不是素数,为其
//赋值1,这样在前面!p[i]判断的时候就可以跳过了
        if(i%prime[j]==0)
//关键 prime数组 中的素数是递增的,当 i 能整除 prime[j],
//那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
               break; 
// 因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。  
            
    }
    }
    return top;
}

希望对大家有帮助,有bug或者是问题,请在下面评论区留言

 

0.0分

0 人评分

  评论区

刚刚删错了一位同学的评论,不好意思啊,我想告诉他的是静下心来,慢慢分析,就不会麻烦了
2017-08-13 08:36:59 | |
明白了
2017-08-05 21:22:45 | |
666,膜拜大神
2017-07-08 11:36:01 | |
  • «
  • 1
  • »