C语言判断一个数是否为素数:C-确定一个数字是否是素数(how to tell if number is prime)

我试图想出一个方法,需要一个整数,并返回一个布尔值说,如果数字是素数与否,我不知道很多 C;会有人愿意给我一些指针?

基本上,我会在 C # 中这样做:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}
154

好的,所以忘了 C 吧。假设我给你一个数字,让你确定它是否是素数。你是怎么做到的?把步骤写清楚,然后担心把它们翻译成代码。

一旦你确定了算法,你就会更容易弄清楚如何编写程序,而其他人也会帮助你。

编辑:这是您发布的 C # 代码:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

这是非常接近有效的 C;C 中没有bool类型,也没有truefalse,因此您需要对其进行一点修改(编辑:Kristopher Johnson 正确地指出 C99 添加了 stdbool.h 标头)。由于有些人无法访问 C99 环境(但您应该使用)

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

这是一个完全有效的 C 程序,可以做你想做的事情。我们可以毫不费力地对其进行一点改进。首先,请注意i总是小于number,因此检查i != number总是成功的;我们可以摆脱它。

此外,您实际上不需要一直尝试除数直到number - 1;当您到达 sqrt(数字)时,您可以停止检查。由于sqrt是一个浮点运算,并且会带来一大堆微妙之处,因此我们实际上不会计算sqrt(number)。相反,我们可以检查i*i <= number

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

不过,最后一件事;您的原始算法中存在一个小错误!如果number为负,或零或一,则此函数将声明该数字为质数。您可能希望正确处理此问题,并且可能希望使number无符号,因为您更可能只关心正值:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

这绝对不是检查数字是否是素数的最快方法,但是它可以工作,而且非常简单。我们几乎不需要修改您的代码!

29

我很惊讶没有人提到这一点。

Use theSieve Of Eratosthenes

细节:

基本上非素数可以被除 1 之外的另一个数字整除

因此:非素数将是素数的乘积。

Eratosthenes 的筛子找到一个素数并存储它。当检查一个新数字的素数时,所有以前的素数都将根据已知的素数列表进行检查。

原因:

此算法 / 问题称为“Embarrassingly Parallel

它创建一个素数集合

它是动态规划问题的一个例子

它的快!

16

斯蒂芬 · 佳能回答得很好!

但是

可以通过观察到所有素数都是 6k ± 1 的形式来进一步改进算法,除了 2 和 3。

这是因为对于某个整数 k 和对于 i =-1 、 0 、 1 、 2 、 3 或 4,所有整数可以表示为 (6k + i);2 除 (6k + 0) 、 (6k + 2) 、 (6k + 4);以及 3 除 (6k + 3)。

因此,一种更有效的方法是测试 n 是否可被 2 或 3 整除,然后检查所有形式为 6k ± 1 ≤ √ n 的数字。

这是测试所有 m 到 √ n 的速度的 3 倍。

int IsPrime(unsigned int number) {
    if (number <= 3 && number > 1) 
        return 1;            // as 2 and 3 are prime
    else if (number%2==0 || number%3==0) 
        return 0;     // check if number is divisible by 2 or 3
    else {
        unsigned int i;
        for (i=5; i*i<=number; i+=6) {
            if (number % i == 0 || number%(i + 2) == 0) 
                return 0;
        }
        return 1; 
    }
}
10

建立一个小素数表,并检查它们是否划分您的输入数字。

如果数字保留为 1,请尝试使用增加基数的伪素性测试。例如,请参见Miller-Rabin primality test

如果你的数字存活到 2,如果它低于一些众所周知的界限,你可以断定它是素数。否则你的答案只会是“可能是素数”。你会在维基页面上找到这些界限的一些值。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(333)
Linux系统安全:系统安全加密 CryptographicException:密钥集不存在
上一篇
苹果手机程序:Apple Watch应用程序检测苹果手表是否与手机配对
下一篇

相关推荐

  • comeandgetyourlove音乐爱就在你身边

    Come and Get Your Love是一首热门的歌曲,由美国摇滚乐队Redbone演唱。这首歌曲于1974年发行,被收录在他们的专辑《Wovoka》中。歌曲以放克曲风为主,旋律活泼,曲调悠扬,歌词朗朗上口,深受歌迷喜爱。…

    2023-06-29 07:47:31
    0 35 68
  • css预编译器: center;}

    CSS预编译器是一种用于构建CSS的工具,它可以将CSS代码转换为更易于管理和维护的格式。它们可以使CSS代码更加灵活,更易于重用,并且可以帮助开发人员更轻松地组织和管理CSS代码。…

    2023-04-30 05:19:08
    0 58 79
  • python中predict函数参数:如何使用Python的predict函数进行机器学习预测

    示例示例predict函数是scikit-learn中的一个函数,用于预测新样本的输出结果。参数:…

    2023-03-30 08:03:12
    0 45 22
  • canvas 官网Bring Your Ideas to Life with Creative Artwork

    Canvas 官网是一个用于创建图形的 HTML5 API,它可以在浏览器中使用 JavaScript 来绘制 2D 图形。它提供了一个可以在网页上绘制图形的强大工具,可以用来创建动画、游戏、数据可视化等。…

    2023-02-28 09:52:08
    0 56 18
  • qt creator快速入门 第3版 pdf从零开始

    Qt Creator快速入门第3版是一本关于Qt Creator的教程书,旨在帮助读者快速掌握Qt Creator的使用。书中介绍了Qt Creator的基本功能,如如何创建项目、编辑代码、调试代码以及创建应用程序等等。书中还提供了一些实例代码,帮助读者更好地理解Qt Creator的用法。…

    2023-05-16 03:03:33
    0 37 70
  • cherry键盘win键不能用:解决Cherry键盘Win键无法使用的措施

    如果您的cherry键盘win键不能用,可能是由于系统设置问题导致的。下面提供一些代码,可以帮助您解决这个问题:打开“控制面板”,然后点击“硬件和声音”,打开“键盘”选项卡。…

    2023-08-27 03:36:33
    0 86 16
  • certificate意思一步一步指南

    示例示例是一种用于证明某个人或机构拥有某种资格或资质的文件。它可以是一种认证,也可以是一种奖励或认可。代码示例:…

    2023-09-14 15:01:58
    0 56 79
  • win10系统ctrl加c不能复制:解决win10系统下Ctrl+C不能复制的问题

    解决方案解决方案答:可能是由于系统快捷键被修改所导致的,可以尝试恢复系统默认快捷键;…

    2023-04-15 00:45:32
    0 35 26

发表评论

登录 后才能评论

评论列表(35条)