【牛客网】HJ99 自守数、OR86 返回小于 N 的质数个数

╰半夏微凉° 2024-03-29 15:39 58阅读 0赞

>  作者：一个喜欢猫咪的的程序员
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> HJ99 自守数 
> 
>  OR86 返回小于 N 的质数个数
> 
> --------------------

## HJ99 自守数 ##

[自守数\_牛客题霸\_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力![icon-default.png?t=MBR7][icon-default.png_t_MBR7]https://www.nowcoder.com/practice/88ddd31618f04514ae3a689e83f3ab8e?tpId=37&&tqId=21322&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking\#:~:text=%E4%B8%8B%E4%B8%80%E9%A2%98-,HJ99%20%E8%87%AA%E5%AE%88%E6%95%B0,-%E9%A2%98%E7%9B%AE][icon-default.png_t_MBR7_icon-default.png_t_MBR7_https_www.nowcoder.com_practice_88ddd31618f04514ae3a689e83f3ab8e_tpId_37_tqId_21322_rp_1_ru_ta_huawei_qru_ta_huawei_question-ranking_text_E4_B8_8B_E4_B8_80_E9_A2_98-_HJ99_20_E8_87_AA_E5_AE_88_E6_95_B0_-_E9_A2_98_E7_9B_AE]**题目描述：**

**描述**

自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数

数据范围：1≤n≤10000

**输入描述：**

int型整数

**输出描述：**

n以内自守数的数量。

示例：

![cc9b67e1f8c74484bdf2760edaa5b062.png][]

--------------------

思路：

**输入一个数n，从0-n中的每一个数i找自守数 ，判断i的平方i2大于10的m次方**

**当i2小于10时，直接让i2=-1，否则取余执行下一次循环。**

**时间复杂度：O（N^2） 空间复杂度：O（1）**

代码：

#include <stdio.h>
    #include <math.h>
    int main()
    {
        int max;
        scanf("%d", &max);
        int num = 0;
        for (int i = 0; i <= max; i++)
        {
            int i2 = i * i;
            int n=0;
            while (pow(10,n)<=i2) 
            {
                n++;
            }
            while (i2 >= i)
            {
                if (i2 == i)
                {
                    num++;
                    break;
                }
                if (i2 < 10)
                {
                    i2 = -1;
                }
                else
                {
                  i2=i2%(int)pow(10, n--);
                }
            }
        }
        printf("%d", num);
        return 0;
    }

--------------------

## OR86 返回小于 N 的质数个数 ##

[返回小于 N 的质数个数\_牛客题霸\_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力![icon-default.png?t=MBR7][icon-default.png_t_MBR7]https://www.nowcoder.com/practice/9e7a88d6a00e404c8418602515a5046c?tpId=182&&tqId=34812&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking\#:~:text=%E4%B8%8B%E4%B8%80%E9%A2%98-,OR86%20%E8%BF%94%E5%9B%9E%E5%B0%8F%E4%BA%8E%20N%20%E7%9A%84%E8%B4%A8%E6%95%B0%E4%B8%AA%E6%95%B0,-%E9%A2%98%E7%9B%AE][N _icon-default.png_t_MBR7_icon-default.png_t_MBR7_https_www.nowcoder.com_practice_9e7a88d6a00e404c8418602515a5046c_tpId_182_tqId_34812_rp_1_ru_ta_exam-all_qru_ta_exam-all_question-ranking_text_E4_B8_8B_E4_B8_80_E9_A2_98-_OR86_20_E8_BF_94_E5_9B_9E_E5_B0_8F_E4_BA_8E_20N_20_E7_9A_84_E8_B4_A8_E6_95_B0_E4_B8_AA_E6_95_B0_-_E9_A2_98_E7_9B_AE]题目描述：

描述

请考虑性能

输入描述：

一个整数N

输出描述：

小于N的质数数量

示例：

![285fca7fb0474acdbe45c227108c9941.png][]

--------------------

代码：

#include <stdio.h>
    int main() {
        int n;
        scanf("%d",&n);
        int num=0;//个数
        for(int i=2;i<n;i++)
        {
            int m=2;
            int flag=0;
            while(m<i)
            {
                if(i%m==0)
                {
                    flag=1;
                    break;
                }
                m++;
            }
            if(flag==0)
            {
                num++;
            }
        }
        printf("%d",num);
        return 0;
    }

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/e3e5fdc967514cfb8b2bd326df070159.png
[icon-default.png_t_MBR7]: https://csdnimg.cn/release/blog_editor_html/release2.2.1/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=MBR7
[icon-default.png_t_MBR7_icon-default.png_t_MBR7_https_www.nowcoder.com_practice_88ddd31618f04514ae3a689e83f3ab8e_tpId_37_tqId_21322_rp_1_ru_ta_huawei_qru_ta_huawei_question-ranking_text_E4_B8_8B_E4_B8_80_E9_A2_98-_HJ99_20_E8_87_AA_E5_AE_88_E6_95_B0_-_E9_A2_98_E7_9B_AE]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/b7adb019975b4f999df74f5bb77ec1d5.png
[cc9b67e1f8c74484bdf2760edaa5b062.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/4b556f717a2c4d948b3b6837f41d070c.png
[N _icon-default.png_t_MBR7_icon-default.png_t_MBR7_https_www.nowcoder.com_practice_9e7a88d6a00e404c8418602515a5046c_tpId_182_tqId_34812_rp_1_ru_ta_exam-all_qru_ta_exam-all_question-ranking_text_E4_B8_8B_E4_B8_80_E9_A2_98-_OR86_20_E8_BF_94_E5_9B_9E_E5_B0_8F_E4_BA_8E_20N_20_E7_9A_84_E8_B4_A8_E6_95_B0_E4_B8_AA_E6_95_B0_-_E9_A2_98_E7_9B_AE]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/1d29483761984d9eabba25cabaf6e531.png
[285fca7fb0474acdbe45c227108c9941.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/6461c886c28c48e8ad4228318efefdc4.png