Almost Prime Numbers UVA - 10539——打表+lower_bound()查找

水深无声 2022-06-14 04:53 123阅读 0赞

Think:  
1题意：输入两个正整数l, r(0 < l <= r < 1e12),统计区间【l, r】中有多少个数满足本身不是素数，但有且仅有一个素因子  
2反思：  
1>int i;  
如果(i \* i > int 存储范围)  
那么 得用 long long 存储 i  
2>lower\_bound()理解使用：  
lower\_bound()如果link数组中查找不到键值返回的是tp位置，注意判断越界情况

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    #define LL long long
    #define ULL unsigned long long
    
    using namespace std;
    
    int tp, v[1040000];
    LL link[1040000];
    
    void Init_prime();
    
    int main(){
    
        Init_prime();
        sort(link, link+tp);
    
        int T;
        LL l, r;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld", &l, &r);
            int t1 = lower_bound(link, link+tp, l) - link;
            int t2 = lower_bound(link, link+tp, r) - link;
            if(t2 == tp || link[t2] > r)
                t2--;
            printf("%d\n", t2-t1+1);
        }
        return 0;
    }
    void Init_prime(){
        tp = 0;
        memset(v, 0, sizeof(v));
        v[1] = 1, v[2] = 0;
        for(LL i = 2; i <= 1000000; i++){
            if(!v[i]){
                for(LL j = i*2; j <= 1000000; j += i){
                    v[j] = 1;
                }
                for(LL k = i*i; k <= 1e12; k *= i){
                    link[tp++] = k;
                }
            }
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-10539

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 10200 Prime Time （打表）(精度太坑了）

UVA 10200 Prime Time （打表） Prime Time Euler is a well-known matematician, and, among

蔚落/ 2022年09月25日 05:19/ 0 赞/ 160 阅读

相关 uva 10140——Prime Distance

题意：题目出的很简单，给定一个数据范围（好吧，又是给定一个范围），然后问你在这个给定的范围内，哪两个相邻素数挨的最近，哪两个最远。思路：这破题数据量很大，如果直接打

客官°小女子只卖身不卖艺/ 2022年08月09日 13:49/ 0 赞/ 29 阅读

相关 uva 10539——Almost Prime Numbers

题意：给定一个区间范围，然后问在这个范围之内有多少个数是素数的整数倍，就是能够化成一个素数乘方的形式思路：首先要打一张sqrt（N+5)大小的素数表，然后对在在这个

淩亂°似流年/ 2022年08月09日 13:49/ 0 赞/ 32 阅读

相关 uva 11105——Semi-prime H-numbers

题意：定义了一种H素数，改素数的定义是能够被4整除余数为1，然后给定一个n值，问1到n中有多少个只被分解成两个H素数的数，题目很绕，H素数和他要球的东西一直搞不明白！

Myth丶恋晨/ 2022年08月09日 13:49/ 0 赞/ 31 阅读

相关 Almost Prime Numbers UVA - 10539——打表+lower_bound()查找

Think: 1题意：输入两个正整数l, r(0 < l <= r < 1e12),统计区间【l, r】中有多少个数满足本身不是素数，但有且仅有一个素因子 2反思：

水深无声/ 2022年06月14日 04:53/ 0 赞/ 124 阅读

相关 Sum of Consecutive Prime Numbers UVA - 1210——素数表+初级dp思想

Think: 1题意：输入正整数n(2 <= n <= 10000),求连续素数之和等于n的方案数 2思路： 1>筛法建立素数表+初级dp思想(从后往前规划得到当前

逃离我推掉我的手/ 2022年06月14日 04:49/ 0 赞/ 184 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 180 阅读

相关 UVA - 10789 - Prime Frequency（素数打表）

题意是给出0-9，A-Z，a-z，组成的字符串，如果字符的个数是素数就输出这个字符。例如ABCC中的C的个数是素数，那么输出C；首先素数打表，剩下的就是如何储存每个

浅浅的花香味﹌/ 2022年06月07日 00:21/ 0 赞/ 217 阅读

相关 Semi-prime H-numbers POJ - 3292 (数学打表)

This problem is based on an exercise of David Hilbert, who pedagogically suggested that

淡淡的烟草味﹌/ 2022年02月20日 13:48/ 0 赞/ 229 阅读

相关 CodeForces 385C Bear and Prime Numbers 素数打表

第一眼看这道题目的时候觉得可能会很难也看不太懂，但是看了给出的Hint之后思路就十分清晰了 Consider the first sample. Overall, t

ゞ浴缸里的玫瑰/ 2021年12月10日 16:45/ 0 赞/ 239 阅读