| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1901 人关注过本帖, 1 人收藏
标题:素数问题的标准模式--求反对者
取消只看楼主 加入收藏
caojulians
Rank: 2
等 级:论坛游民
帖 子:39
专家分:67
注 册:2009-11-15
结帖率:66.67%
收藏(1)
已结贴  问题点数:52 回复次数:2 
素数问题的标准模式--求反对者
    素数问题是一个经典问题,但有无数的初学者有着无穷的烦恼--不是初学者的问题,是教育者的问题,他(她)们没有教这类问题的基本方法:
    问题描述:素数m是仅能被1和m整除的正整数,特别地,1不是素数。
    换个说法就是在2至m-1范围(这个范围再讨论)内至少存在着一个整数因子k能整除m,只要能在指定的范围内找到任一(或几)个整数因子k,就可以下结论“m不是素数”。
    也就是说否定“一个整数m是素数”是容易的,找这个整数因子k--“一票否决!”,但要肯定“一个整数m是素数”是困难的,一定要在指定的范围内无否决票!--不把这个范围内的整数因子都试除一次是不行的!
    下一个问题就是这个范围就是从2到m-1吗?设q=m/k,r=m%k,(不必多解释了吧?q是整除的商、r是整除的余数)。当r为0时,k是一个否决因子,同时q也是一个否决因子!也就是说一次求余运算(%)就蕴含着可能求出两个否决因子k和q!由于k的试除是由小到大的,则q的出现一定是由大到小的--所以找一下k与q会合的地方?当m是个平方数时k==q!m不是平方数呢?k大于sqrt(m)后是不是到达了q的范围了?!

解题步骤:
对于任意给定的整数m,
1.当m<2,则m一定不是素数!
2.假设m是素数
3.取k从2至sqrt(m)
3.1.若m%k==0,否定假设--m一定不是素数,结束第3步
4.若假设没有被否定过,则m是素数,否则m不是素数。

代码设计:
int m,k;
int assume=1;  /*假定m是素数*/
/*获取或生成m*/
if(m<2)
    assume=0;  /*m不是素数*/
else
    for(k=2; k<=sqrt(m); k++)
        if(m%k == 0)
        {
             assune=0;
             break;
         }
if(assume == 1)
     /*m是素数的处理*/
else
     /*m不是素数的处理*/
==================代码优化就不做了:“first make it work, then make it fast!"======

    assume称作标志量----因为这个素数问题是否决容易,所以该标志量一开始假设为“是”(assume=1),然后通过一个循环过程尝试着去“否决”它(assume=0)。
    k称作侯选项,需要 在一个范围内一一列举,又称作穷举侯选项。
    这个方法称作穷举法,在程序设计的入门阶段是一个最基本的方法,并且在程序设计的每一个阶段,当没有想出更好的方法时,穷举法也是打开局面的一种方法。试一试这种方法吧----关键是假设“是”呢?还是假设“不是”呢?

顺便点评一下书上的代码
    for(k=2; k<=sqrt(m);k++)
       if(m%k==0)
           break;
    if(k>sqrt(m))
        /*m是素数*/
    else
        /*m不是素数*/
这是利用k==sqrt(m)+1表示for循环是完整做完了而不是提前break出来的,间接认定m%k==0从没有实现过-->“m是素数”没有被否决过。这个法子表面上“节省”了一个变量assume,但用间接法子去判定一个事实--实在不是一个好法子--至少对初学者不是个好法子(不过若干年前可有人拼命叫好)。

由于素数的题目太多,求证素数的过程最好设计为一个函数
int isprime(int m)
{
    int k;
    if(m<2)
        return 0;               /*小于2的都不是素数*/
    if(m%2 ==0)
        return 0;               /*偶数都不是素数*/
    for(k=3; k*k<=m; k+=2)      /*k从3开始,只选奇数做穷举侯选项*/  
        if(m%k == 0)
              return 0;         /*函数中的return 比break更干脆,退出循环并退出函数*/
    return 1;                  
}                               /*没有使用标志量,一定蕴含着“m是素数”这一假设*/
搜索更多相关主题的帖子: 模式 反对者 素数 
2009-12-01 17:26
caojulians
Rank: 2
等 级:论坛游民
帖 子:39
专家分:67
注 册:2009-11-15
收藏
得分:0 
看来你没有看到下面的文字,标志量的用法--是直接用m%k==0获得的信息(assume=0)还是用间接的循环结束信息去处理后面的工作?这就象脑筋急转弯:小明三兄弟,从大到小叫大毛、二毛,问老三叫什么?
不去用直接信息而用间接信息,素数这个问题不算什么,问题更复杂些呢--当后续处理离当前结论有很大距离--中间有许多代码时,你怎么用?
2009-12-01 18:34
caojulians
Rank: 2
等 级:论坛游民
帖 子:39
专家分:67
注 册:2009-11-15
收藏
得分:0 
楼主:int isprime(int m)
{
    int k;
    if(m<2)
        return 0;               /*小于2的都不是素数*/
    if(m%2 ==0)
        return 0;               /*偶数都不是素数*/
    是吗?那2是什么呢?
=============================
漏了一行
if(m==2)
    return 1;
2009-12-02 05:59
快速回复:素数问题的标准模式--求反对者
数据加载中...
 
   



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

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