汉扬编程 编程大纲 素数的判断「C语言必知必会」

素数的判断「C语言必知必会」

素数的判断「C语言必知必会」

素数的判断「C语言必知必会」

素数判断?这不是小学学的吗?

素数的判断「C语言必知必会」

您先别着急,不管您是小学,初中还是高中,从事什么职业,我相信,坚持看完你一定有收获!

素数的判断「C语言必知必会」

对你有帮助别忘了给我点个赞哦~

素数的判断「C语言必知必会」

我们要判断素数,首先要知道素数的定义。

素数的判断「C语言必知必会」

素数:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。

素数的判断「C语言必知必会」

知道了素数的定义,那么我们应该想一下,如何去判断一个数是否为素数?

素数的判断「C语言必知必会」

一种思路是,我们在每次得到一个数后,都去计算,去尝试因式分解它,看它除了1和自身之外还有没有其他因子另一种是,我们去查阅素数表,看这个数在不在素数表上。那我们就要先得到素数表。

素数的判断「C语言必知必会」

以下除了第一种方法,第2~4种方法都是用第二种思路做的当要判断的目标数很少时,第一种高效。但是当给定的目标数组很多,数也很大时。后面的思路配上高效的查找算法,显然更高效

素数的判断「C语言必知必会」

方法1:暴力求解1-1:稍微动动脑

素数的判断「C语言必知必会」

思想:根据素数的定义思考。素数是大于1的自然数,除了1和自身外,其他数都不是它的因子。 那我们就可以用一个循环,从2开始遍历到这个数减去1,如果这个数都不能被整除,那么这个数就是素数。 也就是说: 给定一个数 n , i 从 2 开始取值,直到 n – 1(取整数),如果 n % i != 0 , n 就是素数 进一步思考,有必要遍历到 n – 1 吗? 除了1以外,任何合数最小的因子就是2,那最大的因子就是 n/2 那我们就遍历到 n/2就足够了

这样我们就可以写出这个算法的核心代码:

int isPrime(int target) {    int i = 0;    if (target <= 1) {        printf("illegal input!\\n");//素数定义        return -1;    }    for (i = 2; i < target / 2; i++) {        if (target % i == 0)            return 0;//不是素数直接返回0    }    return 1;//是素数返回1}

1-2:再进一步

思想:在上面的基础上,其实不需要遍历到 n/2,只需要到 根号n(包含根号n) 就可以了。为什么呢?这是个数学问题,大家自行思考一下。

核心代码:

int isPrime(int target) {    int i = 0;    if (target <= 1) {        printf("illegal input!\\n");//素数定义        return -1;    }    for (i = 2; i <= sqrt(target); i++) {        if (target % i == 0)            return 0;    }    return 1;}

从第二种方法开始,我们都是先完成判断素数数组,然后用二分法去查找判断数组

这里说一下以下三种方法牵扯的概念:

范围:1 ~ 范围上限N范围上限N:判断素数需要用户输入随机素数,这个随机素数的范围是1 ~ N判断素数数组:将数组的下标与1 ~ N的自然数一一对应起来。判断 1到N 的自然数是否为素数,其实就是判断数组的下标是否为素数,如果是 给这个下标所对应的判断素数数组元素赋1,否则赋0比如:我要判断3是否为素数,我们就找到判断素数数组isPrime中的下标为3的元素,即:isPrime[3]如果 3 是素数 isPrime[3] = 1否则 isPrime[3] = 0这样我们在用二分法查找时,查找数组下标就可以,找到下标后返回下标对应的判断素数数组的值。如果是1说明下标对应的自然数是素数,否则不是方法2:用素数表来判断素数思路:如果一个数不能整除比它小的任何素数,那么这个数就是素数这种“打印”素数表的方法效率很低,不推荐使用,可以学习思想

核心代码:

//target:输入的要查找的数//count:当前已知的素数个数//PrimeArray:存放素数的数组int isPrime(int target, int count, int* PrimeArray) {    int i = 0;    for (i = 0; i < count; i++) {        if (target % PrimeArray[i] == 0)            return 0;    }    return 1;}

方法3:普通筛法——埃拉托斯特尼(Eratosthenes)筛法思路:我们的想法是,创建一个比范围上限大1的数组,我们只关注下标为 1 ~ N(要求的上限) 的数组元素与数组下标(一一对应)。 将数组初始化为1。然后用for循环,遍历范围为:【2 ~ sqrt(N)】。如果数组元素为1,则说明这个数组元素的下标所对应的数是素数。 随后我们将这个下标(除1以外)的整数倍所对应的数组元素全部置为0,也就是判断其为非素数。这样,我们就知道了范围内(1 ~ 范围上限N)所有数是素数(下标对应的数组元素值为1)或不是素数(下标对应的数组元素值为0)

用百度百科对埃拉托斯特尼筛法简单描述:要得到自然数n以内的全部素数,必须把不大于 的所有素数的倍数剔除,剩下的就是素数。

核心代码:

//                 判断素数的数组    范围上限Nvoid Eratprime(int* isprime, int upper_board) {    int i = 0;    int j = 0;    //初始化isprime    for (i = 2; i <= upper_board; i++)        isprime[i] = 1;    for (i = 2; i < sqrt(upper_board); i++) {        if (isprime[i]) {            isprime[i] = 1;        }        for (j = 2; i * j <= upper_board; j++) {//素数的n倍(n >= 2)不是素数            isprime[i * j] = 0;        }    }}

方法4:线性筛法——欧拉筛法思路:我们再思考一下上面的埃拉托斯特尼筛法,会发现,在“剔除“非素数时,有些合数会重复赋值。这样就会增加复杂度,降低效率。比如:范围上限N = 16时2是素数,剔除”2 的倍数“,它们是:4,6, 8,10, 12, 14, 163是素数,剔除”3 的倍数”,它们是,6,9,12,156,12是重复的。如何减少重复呢?

核心代码:

void PrimeList(int* Prime, bool* isPrime, int n) {    int i = 0;    int j = 0;    int count = 0;    if (isPrime != NULL) {//确保isPrime不是空指针        //将isPrime数组初始化为 1        for (i = 2; i <= N; i++) {            isPrime[i] = true;        }    }    if (isPrime != NULL && Prime != NULL) {        //从2遍历到范围上限N        for (i = 2; i <= N; i++) {            if (isPrime[i])//如果下标(下标对应着1 ~ 范围上限N)对应的isPrime值没有被置为false,说明这个数是素数,将下标放入素数数组                Prime[count++] = i;            //循环控制表达式的意义:j小于等于素数数组的个数 或 素数数组中的每一个素数与 i 的积小于范围上限N            for (j = 0; (j < count) && (Prime[j] * (long long)i) <= N; j++)//将i强制转换是因为vs上有warning,要求转换为宽类型防止算术溢出。数据上不产生影响            {                isPrime[i * Prime[j]] = false;//每一个素数的 i 倍(i >= 2)都不是素数,置为false                //这个是欧拉筛法的核心,它可以减少非素数置false的重复率                //意义是将每一个合数(非素数)拆成 2(最小因数)与最大因数 的乘积                if (i % Prime[j] == 0)                    break;            }        }    }}

如果你没有理解,可以参考下例

感谢观看,如果有什么错误请指出,谢谢各位!

​有什么不懂也可以直接提出来,我看到就会给大家解答的

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6260.html

嵌入式C语言完全学习笔记(五)

Go 语言 Malloc 的惯用语法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部