理论知识.质数打表

2024-05-30 01:36
文章标签 质数 打表 理论知识

本文主要是介绍理论知识.质数打表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

啊,哈喽,小伙伴们大家好。我是#张亿,今天呐,学的是理论知识.质数打表

为什么需要质数打表

我们已经学习了如何判断一个数是不是质数了,但是还不够。假设要判断很多很多个数是不是质数的时候,之前的学习的方法效率不够高。因为,如果 n 是质数,需要从 2 枚举到 sqrt(n) ,如果题目里面要你几百几千个数逐一判断是否是质数,则很可能会超时。

所谓 质数打表,是指先通过一段比较高效的代码,完成了前期运算,把每一个数是不是质数的信息 表格化 ,在程序的其它位置,如果需要判断一个数是不是质数,只需要去这个预先计算好的表格里面查一下就可以了。

质数打表的算法思路

我们只需要把合数找到,那么自然就能找到质数了。而找合数的思路,则是:从小到大去找质数,每找到一个新的质数,则去把这个质数的倍数标记出来,这些倍数就是合数,而那些自始至终没有被标记过的数就是质数。例如,当我们指导 13 是质数的时候,我们就把 26,39,52,65... 等一系列的合数标记出来。课程E.倍数 的这条题就是演练这个算法思想的。

下面是质数打表的代码:

bool flag[1000001];
void prepare_prime() //质数打表的函数 
{int i,j;for(i=2;i<=1000000;i++){if(!flag[i]) //表示 i是一个质数{for(j=2;i*j<=1000000;j++) //对 j 的倍数(不包含自己)全部设置标记,表示这些数是合数 flag[i*j] = true; }}
}

Copy

执行了上面的 prepare_prime( ) 函数,就产生了 1000000 以内的质数表了。当 flag[i] 为true,表示 i 是合数,flag[i] 为 false 则表示 i 是质数。 1 是特殊的,1 既不是质数又不是合数,单独判断。

常见错误

本来题目要你找出 n 以内的素数,但是你打表的时候的第一层循环只循环到 sqrt(n) ,这是错误的,这会漏掉了很多 比 sqrt(n) 大的质数。

这篇关于理论知识.质数打表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1015213

相关文章

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

uva 10916 Factstone Benchmark(打表)

题意是求 k ! <= 2 ^ n ,的最小k。 由于n比较大,大到 2 ^ 20 次方,所以 2 ^ 2 ^ 20比较难算,所以做一些基础的数学变换。 对不等式两边同时取log2,得: log2(k ! ) <=  log2(2 ^ n)= n,即:log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ,其中 n 为 2 ^

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

高精度打表-Factoring Large Numbers

求斐波那契数,不打表的话会超时,打表的话普通的高精度开不出来那么大的数组,不如一个int存8位,特殊处理一下,具体看代码 #include<stdio.h>#include<string.h>#define MAX_SIZE 5005#define LEN 150#define to 100000000/*一个int存8位*/int num[MAX_SIZE][LEN];void

数据仓库理论知识

1、数据仓库的概念          数据仓库(英文:Date Warehouse,简称数仓、DW),是一个用于数据存储、分析、报告的数据系统。数据仓库的建设目的是面向分析的集成化数据环境,其数据来源于不同的外部系统,其结果开放给不同外部应用使用,为企业提供决策支持; 2、数据仓库的主要特征 数据仓库是面向主题性(Subject-Oriented )、集成性(Integrated)、非易

js算法题,给任意一个偶数,找出他的所有的质数因子

/*给任意一个偶数,找出他的所有的质数因子*/ function primeFactor(n){     var factors=[],            divistor=2;     if(typeof n !=='number'||!Number.isInteger(n)){          return 0;     }; //如果不是偶数返回0,如果是0,返回0

算法---计数质数(Java)

题目:计数质数 给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。 示例 1: 输入:n = 10 输出:4 解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2: 输入:n = 0 输出:0 示例 3: 输入:n = 1 输出:0 提示: 0 <= n <= 5 * 106 解决方法:(埃氏筛) 思路: 算法由希腊数学家厄拉多塞(\rm

leetcode 204:计数质数

int countPrimes(int n) {if(n<=0)return 0;int c=0;for(int i=2;i<n;i++){int flag=0;for(int j=2;j<=std::sqrt(i);j++){if(i%j==0){flag=1;break;}}if(flag==0)c++;}return c;}

第九届中国大学生程序设计竞赛(秦皇岛)-(CCPC2023-Qinhuangdao F - 质数之谜(DP)

题意 给定一个序列,修改最少数量的元素使得任意i属于[1,n-1],q[i]+q[i+1]都为质数,输出最小修改次数 思路 首先手玩的过程中可以发现,     如果因为前面一个数字和自己相加不是质数然后我把自己变成了奇数,那么如果我后面一个数字是偶数     可以发现自己肯定能找到另一个奇数使得和前面相加互质并且和后面相加也互质     举个例子:假设为2 8 10,我此时是8,我发现2+

力扣刷题--762. 二进制表示中质数个计算置位【简单】

题目描述🍗 给你两个整数 left 和 right ,在闭区间 [left, right] 范围内,统计并返回 计算置位位数为质数 的整数个数。 计算置位位数 就是二进制表示中 1 的个数。 例如, 21 的二进制表示 10101 有 3 个计算置位。 示例 1: 输入:left = 6, right = 10 输出:4 解释: 6 -> 110 (2 个计算置位,2 是质数) 7