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

水深无声 2022-06-14 04:53 88阅读 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 条评论，88人围观）

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

相关阅读

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

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

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

相关 UVA - 524 Prime Ring Problem

Description A ring is composed of n (even number) circles as shown in diagram. Put natu

朱雀/ 2022年07月10日 11:28/ 0 赞/ 112 阅读

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

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

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

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

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

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

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

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

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

相关 UVA - 10924 - Prime Words (素数)

输入一个由大小写字母组成的字符串，每个字符代表着不同的数字，计算出这个字符串的数值，判断是否是素数；首先我们打个素数表；然后利用ascll码存入数组中，然后判断就o

r囧r小猫/ 2022年06月07日 00:23/ 0 赞/ 94 阅读

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

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

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

相关 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 赞/ 146 阅读

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

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

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

相关 UVA P12101 【Prime Path】

题库：UVA 题号：12101 题目：Prime Path link ：[https://www.luogu.org/problemnew/sho

素颜马尾好姑娘i/ 2021年12月03日 11:17/ 0 赞/ 138 阅读