uva 10539——Almost Prime Numbers

淩亂°似流年 2022-08-09 13:49 2阅读 0赞

题意：给定一个区间范围，然后问在这个范围之内有多少个数是素数的整数倍，就是能够化成一个素数乘方的形式  
  
思路：首先要打一张sqrt（N+5)大小的素数表，然后对在在这个区间的数依次进行枚举做因数分解，最后把结果加起来即可！  
  
code：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <cmath>
    using namespace std;
    
    typedef long long ll;
    const int N=1000010;
    ll pri[N],vis[N],len=0;
    
    void tab()
    {
        
        for (int i=2;i<N;i++)
        {
        
            if (vis[i]==1) continue;
            pri[len++]=i;
            for (int j=i;j<N;j+=i)
                vis[j]=1;
        }
    }
    int main()
    {
        
        tab();
        int T;
        scanf("%d",&T);
        while (T--)
        {
        
            ll a,b;
            scanf("%lld %lld",&a,&b);
            ll ans=0;
            for (ll i=0;i<len;i++)  //分解质因数
            {
        
                    ll t=pri[i]*pri[i];
                        if (t>b) break;
                while (t<=b)
                {
        
                    if (t>=a) ans++;
                    t*=pri[i];
                }
            }
            printf("%lld\n",ans);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Sum of Consecutive Prime Numbers

4.Sum of Consecutive Prime Numbers Some positive integers can be represented by a

怼烎@/ 2023年07月08日 02:52/ 0 赞/ 7 阅读

相关 uva 10539——Almost Prime Numbers

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

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

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

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

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

相关 uva 138——Street Numbers

题意：一个老师闲来无事就从他家门口向前走，然后累加门牌数，最后发现向前走和向后累加到的门牌数一样，然后让求该老师家的门牌数，枚举出前6个。思路：假设门牌数为1-n，

缺乏、安全感/ 2022年08月09日 13:49/ 0 赞/ 107 阅读

相关 uva10780 - Again Prime? No time

uva10780 - Again Prime? No time Again Prime? No time. The problem statement i

ゝ一纸荒年。/ 2022年08月09日 13:45/ 0 赞/ 3 阅读

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

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

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

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

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

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

相关 UVA - 10394 - Twin Primes（素数对）

定义了一个素数对的概念，就是如果p是素数的话，p+2也是素数的话，那么（p，p+2）就是一组素数对；那么我们在打素数表的时候，顺便判断i-2是否是素数即可； i

电玩女神/ 2022年06月07日 00:23/ 0 赞/ 141 阅读

相关 Sum of Consecutive Prime Numbers

一些正整数能够表示为一个或多个连续素数的和。给定一个正整数，有多少个这样的表示？例如，整数53有两个表示5+7+11+13+17和53；整数20没有这样的表示。注意加法操

约定不等于承诺〃/ 2022年03月29日 12:58/ 0 赞/ 166 阅读

相关 UVA P12101 【Prime Path】

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

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