无平方因子数

比眉伴天荒 2022-06-09 09:21 295阅读 0赞

题目:

给出正整数n和m，区间\[n,m\]内的“无平方因子”的数有多少个？整数p无平方因子当且仅当不存在k > 1,使得p是k \* k的倍数。1 <= n <= m <= 10 ^ 12,m - n <= 10 ^ 7

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <math.h>
    #include <cstring>
    using namespace std;
    const int maxn=100005;   //求出根下m内的质数即可
    int p[maxn];
    int prim[maxn];
    int len=0;
    void zhishu(int m)  //找出根下m以内的质数
    {
        memset(p,0,sizeof(p));
        int k=sqrt(m+0.5);
        p[1]=1;
        for(int i=2; i<=k; i++)
        {
            if(!p[i])
                for(int j=i*i; j<=m; j+=i)
                    p[j]=1;
        }
        len=0;
        for(int i=1; i<=m; i++)
        {
            if(!p[i])
                prim[len++]=i;
        }
    }
    
    int pd(int num)   //判断这个数是否是平方因子
    {
        for(int i=0; i<len; i++)
            if(num%(prim[i]*prim[i])==0)
                return 0;
        return 1;
    }
    int main()
    {
        int n,m;
        long long sum;
        while(scanf("%d%d",&n,&m)!= EOF)
        {
            zhishu(m);
            sum=0;
            for(int i=n; i<=m; i++)
                if(pd(i))
                    sum++;
            printf("%lld\n",sum);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关平方数之和

633. 平方数之和 > 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。示例 1： > 输入：c = 5 >

曾经终败给现在/ 2024年04月06日 10:04/ 0 赞/ 131 阅读

相关求一个数所有因子个数和因子和

一、求一个数所有因子个数若能整除i，则不断除i，并记录i的次数。则除到最后存在两种情况当x == 1，这说明 x 没有其他因子了，得到答案；当x !=

柔情只为你懂/ 2023年07月02日 07:28/ 0 赞/ 81 阅读

相关 Java—平方数

Java—平方数 Description 飞飞特别喜欢平方数，可是他数学并不好，你能帮他计算n与m之间所有平方数之和吗？提示：若一个整数的开方还是整数，它就是平

我会带着你远行/ 2022年12月10日 08:37/ 0 赞/ 231 阅读

相关回文平方数

回文数是指从左向右念和从右向左念都一样的数。如123321就是一个典型的回文数。给定一个进制B(2≤B≤20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）

旧城等待，/ 2022年09月30日 15:52/ 0 赞/ 218 阅读

相关排它平方数

小明正看着 203879 这个数字发呆。原来，203879 \ 203879 = 41566646641 这有什么神奇呢？仔细观察，2

待我称王封你为后i/ 2022年08月04日 16:40/ 0 赞/ 208 阅读

相关 uva 10110 平方数的因子有奇数个

这题就是判断给定的数的因子的个数，多写几个看看其实就知道了，只有平方数的因子个数是奇数，别的数的因子个数全部都是偶数。 include<bitset>

た入场券/ 2022年08月04日 00:47/ 0 赞/ 196 阅读

相关平方数

平方数 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

待我称王封你为后i/ 2022年07月16日 05:21/ 0 赞/ 250 阅读

相关平方数

Problem Description 飞飞特别喜欢平方数，可是他数学并不好，你能帮他计算n与m之间所有平方数之和吗？提示：若一个整数的开方还是整数，它就是平方数。

秒速五厘米/ 2022年06月16日 10:44/ 0 赞/ 395 阅读

相关无平方因子数

题目: 给出正整数n和m，区间\[n,m\]内的“无平方因子”的数有多少个？整数p无平方因子当且仅当不存在k > 1,使得p是k \ k的倍数。1 <= n <= m <=

比眉伴天荒/ 2022年06月09日 09:21/ 0 赞/ 296 阅读

相关对称平方数

时间限制：1秒空间限制：32768K 热度指数：14383 [ 算法知识视频讲解][Link 1] 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自

系统管理员/ 2022年01月07日 15:17/ 0 赞/ 319 阅读