搜索结果
查询Tags标签： 质数，共有 187条记录-
511 试除法 判质数
视频链接： Luogu P5736 【深基7.例2】质数筛#include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std;bool isprime(int x){ //判质数if(x == 1) return 0;for(int i=2; i<=sqrt(x); i++)if(x%i …
2022/9/12 23:55:11 人评论 次浏览 -
道长的算法笔记：数论基础汇总
质数判定与筛选给定一个正整数 \(N\)，如果存在一个数 \(T\)，T 满足\((2\leq T \leq N -1)\) 则称 \(N\) 是一个合数，如果不存在这样这样的因数 \(T\)，则称\(N\) 质数。简单来说，一个数\(N\) 如何仅能被 \(1\) 与 \(N\) 本身整除，则称这个数字是质数，或称素数(Prime…
2022/9/3 14:25:25 人评论 次浏览 -
Millar-Rabin 米勒罗宾算法小结 （内附费马小定理证明以及二次探测定理证明）
因为他我学了龟速乘 Millar-robin 米勒罗宾 这个小东西是用来素数判定的，且听我细细道来。 前置知识肥妈小定理 又名费马小定理 ： 当一个数 \(x\) 不是一个质数 \(p\) 的倍数时有： \[x^{p-1} \equiv 1 \pmod{p} \]证明： 对于一个序列 \[b = \left \{1,2,3....p-1\rig…
2022/9/2 1:25:35 人评论 次浏览 -
质数判定的常数优化
注意：下面可能有部分数学符号使用不规范，看懂就行。 如何迅速判断 \(n\) 是否为质数？ 方法一 枚举 \(i\) 满足 \(1 < i < n\)，则 \(n\) 不是质数，当且仅当全部的 \(i \nmid n\)。 时间复杂度 \(O(n)\)。 bool isp(int n) //isp = is_prime {if (n <= 1) ret…
2022/8/26 6:23:33 人评论 次浏览 -
AT2286 题解
题目传送门 小学生又双叒叕来写题解啦！ 这题要用到因数个数定理，没学过的童鞋自己了解一下。 由于和质数有关，我使用质数筛法。 我使用较快的欧拉筛法算质数（想学就做这题）。 事实上，由于范围不大，使用普通的埃氏筛也行。 最后一个问题是：枚举质因数个数。 相信这…
2022/8/25 6:24:13 人评论 次浏览 -
[AcWing 197] 阶乘分解
点击查看代码 #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n; vector<int> primes; bool st[N];void get_primes(int x) {for (int i = 2; i <= x; i ++) {if (!st[i])primes.push_back(i);for (auto p …
2022/8/8 6:25:25 人评论 次浏览 -
求质数的简单算法
输入数字n，输出小于等于n的所有质数。 算法是简单的试除法，稍作优化，假设当前枚举数字为x，从2到sqrt（x）依次看看x是否能被整除，能被整除就不是质数，否则就是质数。#include<iostream> using namespace std; int main() {int n;cin >> n;for (int i …
2022/7/27 14:25:16 人评论 次浏览 -
筛质数（三种做法）
通常针对多个数筛质数 给定一个正整数 $ n $，请你求出 $ 1 \sim n $ 中质数的个数。 输入格式 共一行，包含整数 $ n $。 输出格式 共一行，包含一个整数，表示 $ 1 \sim n $ 中质数的个数。 数据范围 $ 1 \le n \le 10^6 $ 输入样例： 8输出样例： 4想法 三种筛法： 1. …
2022/7/24 6:25:16 人评论 次浏览 -
筛法求欧拉函数之和
题目描述 求\(1\sim n\)每个数欧拉函数之和 想法如果\(i\)是质数 \(\varphi (i) = i - 1\)质数\(i\)只有\(1\)和\(i\)两个因数，\(i\)不和\(i\)本身互质，因数只有一个\(1\)，所以互质的数就有\(i-1\)个如果\(i\)不是质数\(i \% j = 0\) \(j\)是质数 则\(j\)即\(i\)的一个…
2022/7/24 6:24:07 人评论 次浏览 -
快速幂求逆元
快速幂求逆元 给定 $ n $ 组 $ a_i, p_i $，其中 $ p_i $ 是质数，求 $ a_i $ 模 $ p_i $ 的乘法逆元，若逆元不存在则输出 impossible。 注意：请返回在 $ 0 \sim p-1 $ 之间的逆元。 乘法逆元的定义若整数 $ b，m $ 互质，并且对于任意的整数 $ a $，如果满足 $ b|a $，…
2022/7/24 6:23:50 人评论 次浏览 -
Math
题目大意： JATC的数学老师为了不让同学们感到厌倦，总是出一些有趣的题目。今天的题目是这样的： 给定一个整数n，您可以对它进行如下操作：乘以x：把n乘上x（x是任意正整数）。 开方：把n的值更新为sqrt{n} (前提是\sqrt{n}必须为整数)。您可以对这些操作进行零次至任意…
2022/7/11 23:22:35 人评论 次浏览 -
[笔记] 求质数的原根
素数的原根的定义：若\(g^0,g^1 \cdots g^{p-1}\)在mod p意义下各不相同，则g是p的一个原根。质数的最小的原根通常很小，所以从2开始枚举每一个正整数，判断其是否为p的原根。 判断的方法：如果g不是p的原根，则存在\(0\leq i < j \leq p-1\)满足\(g^i≡g^j\)(mod p)，…
2022/7/8 23:23:37 人评论 次浏览 -
python2022-06-22
""" 题目描述: 给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。 如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)） [2,3,5,7] 输入描述： 输入包括一个整数n,(3 ≤ n &l…
2022/6/23 5:19:53 人评论 次浏览 -
JavaScript问题: 1-100质数
javscript----1-100质数 质数只能被1和本身整除的数var count = 0;//计数器var sum = 0;//累加器for(var i=2;i<100;i++){var flag = true;//默认每个i都是质数for(var j=2;j<i;j++){if(i%j==0){//能被小于自身的数整除flag = false;break;//跳出里面的for循环}}if(…
2022/5/26 1:50:04 人评论 次浏览 -
2040：【例5.7】筛选法找质数
2040：【例5.7】筛选法找质数 时间限制: 1000 ms 内存限制: 65536 KB提交数: 11392 通过数: 7731 【题目描述】用筛法求出n(2≤n≤1000)n(2≤n≤1000)以内的全部质数。【输入】输入nn。【输出】多行，由小到大的质数。【输入样例】 10 【输出样例】 2 3 5 7#i…
2022/5/24 23:52:46 人评论 次浏览
