| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3391 人关注过本帖
标题:求助,帮我完善一下。用筛法求出n以内的素数,n由键盘输入,用数组表示n个数 ...
只看楼主 加入收藏
SZHLYJ
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2016-6-28
结帖率:0
收藏
已结贴  问题点数:10 回复次数:3 
求助,帮我完善一下。用筛法求出n以内的素数,n由键盘输入,用数组表示n个数的集合。
#include<stdio.h>
#include<math.h>
#define N 100000000
void prime(int n);
int isPrime[N + 1];
int main()
{
    int i,n;
    scanf("%d", &n);
    prime(n);/*调用筛选素数函数*/
    for (i = 0; i <= n; i++)/*输出n以内的所有素数*/
    {
        if (isPrime[i] == 1)
            printf("%d\n", i);
    }
}
/*筛选从2到n之间的素数,筛选结果存入数组isPrime*/
void prime(int n)
{
    int i, j, m;
    for (i = 0; i <= n; i++)/*将isPrime数组元素初始化为1*/
        isPrime[i] = 1;
    isPrime[0] = isPrime[1] = 0;/*0和1不是素数,所以将相应的元素设置为0*/
    m = (int)sqrt(n);
    for (i = 2; i <= m; i++)
    {
        if (isPrime[i])/*筛选掉素数的整数倍*/
        {
            for (j = 2 * i; j <= n; j = j + i)
                isPrime[j] = 0;
        }
    }
}
搜索更多相关主题的帖子: include 键盘 元素 
2016-06-28 02:03
SZHLYJ
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2016-6-28
收藏
得分:0 
已经为这道题夜不能寐啦,只能做到输入100000000以内的数顺利执行,我想让随便输入一个整数,不管多大都能顺利执行,怎么修改?
2016-06-28 02:04
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:10 
以下是引用SZHLYJ在2016-6-28 02:04:29的发言:

我想让随便输入一个整数,不管多大都能顺利执行
做不到,因为“计算机算法(计算机算法!=数学算法)”的定义中有“有限资源”的限制,起码你不可能超越整个宇宙的状态去存储你这个无限大的数。因此,你只能使得这个数尽可能的大,做不到“不管多大”。

对于你的算法,筛选法就是空间换时间,也就是限制在于 int isPrime[N + 1]; 上。
第一,你可以换用64位的操作系统,如果你的主板支持,它最大可以支持128G的内存
第二,你可以从算法上改良,比如你现在用一个int去表示一个布尔状态,这是浪费,只需要一个bit就行了,这样就可以扩大32背;另外,偶数除了2之外,其它都不是质数,因此可将偶数剔除,这样一来上限又扩大了一倍。
2016-06-28 08:32
SZHLYJ
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2016-6-28
收藏
得分:0 
回复 3楼 rjsp
谢谢啦
2016-06-28 09:20
快速回复:求助,帮我完善一下。用筛法求出n以内的素数,n由键盘输入,用数组表示 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026643 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved