首页
DreamJudge
院校信息
考研初试
机试真题
讨论区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
红鲤鱼
2025年2月26日 23:26
非素数个数 题解:
P1701
回复 1
|
赞 27
|
浏览 769
如果说2是素数,则2的倍数绝对不是素数,同理3也一样。 那么筛选素数,就是从2开始,假定一开始都是素数,第一次循环会将2的倍数的数全部置1(表示不为素数),之后从3开始。 可以发现6即是2的倍数又是3的倍数,所以可以进一步的从i的平方开始,优化,当然不优化从i+i开始也行。 #include<bits/stdc++.h> using namespace std; //bool sushu(int n){ // for(int i=2;i<=sqrt(n);i++){ // if(n%i==0){ // ...
Candour
2025年2月23日 16:22
非素数个数(线性筛+前缀和)题解:
P1701
回复 0
|
赞 8
|
浏览 721
#include<bits/stdc++.h> using namespace std; const int N = 1e7 + 10; int l, r; int primes[N], cnt, s[N]; bool st[N]; void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(!st[i]) primes[cnt ++] = i; for(int j = 0; primes[j] <= n/ i; j ++) { ...
iRR
2024年6月13日 16:31
非素数个数 题解:
P1701
回复 0
|
赞 9
|
浏览 1.1k
#include<bits/stdc++.h> using namespace std; int a,b; int isvisit[10000001]; int prime[10000001]; int c = 1; // 素数筛 void isprime() { for(int i = 2;i<10000001;i++) isvisit[i] = 0; for(int i = 2;i<10000001;i++) { if(isvisit[i] == 0) prime[c++] = i; for(int j = 1;j...
Pstary
2023年9月15日 16:05
非素数个数 题解:
P1701
回复 0
|
赞 12
|
浏览 2.0k
#include<stdio.h> #include<string.h> #include<stdbool.h> #include<math.h> #define N 10000000 /* 埃拉托斯特尼筛法是一种用于找出一定范围内所有素数的算法: 1.首先,创建一个包含从2到所需范围内所有数字的列表。 2.从最小的素数2开始,将其标记为素数,并将其倍数(除了自身)标记为合数。 3.继续找到下一个未被标记的素数,将其标记为素数,并将其倍数标记为合数。 4.重复步骤3,直到找到的素数的平方大于所需范围的...
h1h
2023年7月4日 11:59
非素数个数 题解:
P1701
回复 0
|
赞 4
|
浏览 1.5k
#include<stdio.h>//c语言版本 #define N 10000000 int primes[N],cnt; int st[N]; void get_primes(int n) { st[1]=0; for(int i=2;i<=n;i++) { if(!st[i]) { ...
My_opt
2022年4月30日 02:56
c++
P1701
回复 1
|
赞 2
|
浏览 4.7k
#include <iostream> using namespace std; const int N = 1e7 + 10; int a, b, cnt; int primes[N]; bool st[N]; int get_primes(int x) { for (int i = 2; i <= x; i ++ ) { if (!st[i]) primes[cnt ++] = i; for (int j = 0; primes[j] <= x / i; j ++ ) { st[primes[j] *...
James
2021年3月20日 19:48
筛法素数
P1701
回复 0
|
赞 0
|
浏览 9.5k
#include <iostream> #include <algorithm> #include <stack> #include <string.h> #include <stdio.h> #include <queue> #include <math.h> using namespace std; const int maxn=1e7+5; int vis[maxn]; int prime[maxn/2]; int idx=1; void f(){ &nb...
寂寞圣哲
2020年4月17日 19:53
java实现素数筛选法
P1701
回复 0
|
赞 1
|
浏览 11.5k
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int a=sc.nextInt(); int b=sc.nextInt(); int count=0; boolean flag[]=new boolean[b+1]; //记录数的状态,默认都是素数 for(int i=...
wudiyiyi
2020年4月15日 23:26
1e7的数据,所以筛法(打表)
P1701
回复 0
|
赞 3
|
浏览 11.6k
#include <bits/stdc++.h> using namespace std; const int N=1e7+7; int l,r; bool p[N]; int main() { for(int i=2;i<N;i++) { if(p[i]==0)///如果是素数 { for(int ...
莫小七
2020年4月12日 21:51
1701非素数个数(考试前要复习筛查法)
P1701
回复 3
|
赞 17
|
浏览 14.5k
#include<iostream> using namespace std; bool a[10000001] = { true }; void Prime(long long end) { for (long long i = 2; i <= end; i++) { a[i] = true; } for (long long i = 1; i * i <= end; i++) { if (a[i]) {//素数的倍数全部不是素数置false for (long long j = i * i; j &...
题目
非素数个数
题解数量
10
发布题解
在线答疑
热门题解
1
非素数个数 题解:
2
1701非素数个数(考试前要复习筛查法)
3
非素数个数 题解:
4
非素数个数 题解:
5
非素数个数(线性筛+前缀和)题解:
6
非素数个数 题解:
7
1e7的数据,所以筛法(打表)
8
c++
9
java实现素数筛选法
10
筛法素数