首页 > 其他分享 >P1835 素数密度

P1835 素数密度

时间:2023-04-11 12:22:14浏览次数:42  
标签:P1835 int init long 素数 密度 1e6 include

给定区间 [L,R](1≤R<(1<<30)  R−L≤1e6 ),请计算区间中素数的个数。

筛出 sqrt(R) 的质数p, 遍历 L~R 的数,看能否被p 约分,也就是合数,打个标记

 

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ; 
  const int M=1e6+30;
 #define int long long
 int vis[M];
 int b[M],prime[M],tot,n;
 
 void init(int top){
 	 memset(b,1,sizeof b);
     b[1]=0;
     
     int i,j;
     for(i=2;i<=top;i++){
         if(b[i]) prime[++tot]=i;
         
        for(j=1;j<=tot&&i*prime[j]<=top;j++){
             b[i*prime[j]]=0;
             if(i%prime[j]==0) break;
        } 
     }
 }
 signed main(){
 	int L,R;
 	cin>>L>>R; L= L==1?2:L;
 	init(1e6);
 	for(int i=1;i<=tot;i++){
 		int t=prime[i];
 		int k=(L+t-1)/t*t>2*t?(L+t-1)/t*t:2*t;
 		
 		for(int j=k;j<=R;j+=t) vis[j-L+1]=1;
 	}
 	int cnt=0;
 	for(int i=L;i<=R;i++) if(vis[i-L+1]==0) cnt++; 
 	cout<<cnt;
 }
 
 
 

 

标签:P1835,int,init,long,素数,密度,1e6,include
From: https://www.cnblogs.com/towboa/p/17305822.html

相关文章

  • (5)使用函数验证哥德巴赫猜想:任何一个不小于6的偶数均可表示为两个奇和。输入两个正整数
    #include<stdio.h>#include<math.h>intprime(intm){  inti;  if(m<2)    return0;  for(i=2;i<=sqrt(m);i++){    if(!(m%i))      return0;  }  return1;}intmain(){  intm,n,flag;  printf("Enterm,......
  • Khan公开课 - 统计学学习笔记:(三)随机变量、概率密度、二项分布、期望值
    随机变量RandomVariable随机变量和一般数据上的变量不一样,通常用大写字母表示,如X、Y、Z,不是个参数而是function,即函数。例如,下面表示明天是否下雨的随机变量X,如下。又例如X=每小时经过路口的车辆,随机变量是个描述,而不是方程中的变量。随机变量有两种,一种是离散的(discrete),一种是连......
  • Python求100以内的素数常用方法!
    与其他编程语言对比,Python拥有十分独特的优势代码量少,相同功能其他编程语言需要上百行代码才可以实现,而Python只需要十几行就可以实现。而且在Python中,我们只需要学会一些基础的语法就可以实现简单的数值计算,那么Python求100内的所有素数方法是什么?具体内容请看下文。质数......
  • 记录欧式筛法筛选素数
    点击查看代码voidgetPrime(longlongn,vector<int>&prime,vector<bool>&isPrime){isPrime[1]=false;for(inti=2;i<n;++i){if(isPrime[i]){prime.emplace_back(i);}for(constint&a......
  • 判断100内的素数
    #include<stdio.h>#include<math.h>intmain(){inti=0;for(i=1;i<=100;i++){intj=0;for(j=2;j<=sqrt(double(i));j++){if(i%j==0){break;}}if(j>sqrt(double(i))){printf("%d",i);}}return0;}  问题:    在运行......
  • C - 素数密度
    题解在代码里,如下点击查看代码#include<bits/stdc++.h>typedeflonglongLL;usingnamespacestd;//如果一个数n不是质数,就一定有非一的因数x<=sqrt(n);constintN=5e4;//因为所给题目最大到(1<<31)所以只需要求出来1~N之间的所有质数就行constintM=1e6+7;intid......
  • 欧拉筛法求素数
    在开筛之前,我们要理解一个很好理解的概念,任何一个合数可以拆成一个最小素数和另一个数(可能质数可能合数)的乘积这个最小素数即为这个合数的最小质因子//比如12=2*6,此时2就是12的最小质因子,当然亦有12=3*4,可以看到3也是12的质因子,但不是最小的质因子//而且,对于一合数a=b*q,b为a的最......
  • 素数环
    #include<cstdio>#include<iostream>#include<cstring>usingnamespacestd;boolisprime[40];//用于判断是否为素数boolisused[20];//用于判断是否重复使用。i......
  • C01素数之和
    publicclassA01素数之和{publicstaticvoidmain(String[]args){intsum=0;//累加求和for(inti=2;i<=100;i++){if(isSS(i)){//如果i是素数,就累加到su......
  • 6-2 计算素数和
    本题要求计算输入两个正整数x,y(x<=y,包括x,y)素数和。函数isPrime用以判断一个数是否素数,primeSum函数返回素数和。实现代码:defisPrime(x):foriinrange(2,x):......