uva 11105——Semi-prime H-numbers

Myth丶恋晨 2022-08-09 13:49 2阅读 0赞

题意：定义了一种H素数，改素数的定义是能够被4整除余数为1，然后给定一个n值，问1到n中有多少个只被分解成两个H素数的数，题目很绕，H素数和他要球的东西一直搞不明白！  
  
思路：最好的办法是打一张H素数表，然后利用这张素数表，打印另外一张符合条件的素数表，当然直接去打可能会出现存不下的现象，反正给定的n都是4k+1，那么可以只打k的一张表来节省空间，打素数的时候也要格外注意，我就是因为没有注意重复“莫名”地wa了两次，具体的实现，就有点像筛素数的方法了。  
  
code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <set>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=1000005;
    int f[N/4];        //节省空间
    int vis[N];
    
    void shui()
    {
        
        memset(vis,-1,sizeof(vis));    //两次筛，一次筛H素数，另一次筛符合条件的数
        int s=0;
        for (int i=5;i<N;i+=4)
            for (int j=5;i*j<N;j+=4)
            {
        
                if (vis[i]==-1&&vis[j]==-1) vis[i*j]=1;
                else vis[i*j]=0;
            }
        for (int i=1;i<N/4;i++)
        {
        
            if (vis[i*4+1]==1) s++;
            f[i]=s;
        }
    }
    int main()
    {
        
        //freopen("out.txt","w",stdout);
        shui();
        int n;
        while (~scanf("%d",&n)&&n)
            printf("%d %d\n",n,f[(n-1)/4]);
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 uva 12938

题目大意：题目的大概意思就是，给你一个四位数，换动任何一个数可以得到完全平方数，如果可以得到输出可能种类数，（注意：第一个数不可以换成0）题目解析：这是一个简

素颜马尾好姑娘i/ 2022年06月10日 00:11/ 0 赞/ 159 阅读

相关 uva 12934

题目大意：给你一个K，问k是否是两个数阶乘相除得到的，输出最小的两个数题目解析：这是一个简单的数学题，首先当k=1时，Impossible，如果是奇数直接

青旅半醒/ 2022年06月10日 00:11/ 0 赞/ 11 阅读

相关 uva 12932

题目大意：题目的意思就是要找出行列和最大的位置，题中给了一种错误的算法，就是首先先找和最大的一行，然后再找列最大的一行，然后交点就是所要求的值，但是交点处的值多算了一便，如

Dear 丶/ 2022年06月10日 00:11/ 0 赞/ 130 阅读

相关 uva 12930

![Image 1][] 题目大意：题目的意思是给定两个数，比较大小，但是这是个很多位的数题目解析：这是一个简单的模拟题，非常的水，就是一个字符串模拟

旧城等待，/ 2022年06月10日 00:11/ 0 赞/ 131 阅读

相关 UVA 414

include<iostream> include<string> include<cstring> using namespace std;

╰半夏微凉°/ 2021年11月17日 21:36/ 0 赞/ 280 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 233 阅读

相关 Uva 540

include<iostream> include<queue> include<cstring> include<string> us

Love The Way You Lie/ 2021年11月17日 21:20/ 0 赞/ 320 阅读

相关 uva 127

开始用的是vector<sta include<iostream> include<cstring> include<vector> incl

快来打我*/ 2021年11月17日 21:18/ 0 赞/ 250 阅读

相关 UVA Intervals

UVA Intervals Description 有n个区间，在区间\[ai，bi\]中至少取任意互不相同的ci个整数。求在满足n个区间的情况下，至少要取多

你的名字/ 2021年11月10日 02:26/ 0 赞/ 257 阅读