翻译代码#include <stdio.h> #include <string.h> #define N 10010 #define M 20010 int cnt[N]; //cnt[i],i出现的次数 int main(){ int n, m,t; while(scanf("%d%d", &n, &m), n + m){ memset(cnt, 0, sizeof(cnt)); int i, j, res = 0; for(i = 0; i < m; i++){ scanf("%d", &t); cnt[t]++; } for(i = 1; i <= n; i++){ if(cnt[i] > 1){ res ++; } } printf("%d\n", res); } return 0; }

这是一段 C 语言代码，主要功能是读入两个整数 n 和 m，接下来读入 m 个整数，统计这些整数中出现次数大于 1 的数的个数，并输出这个个数。

具体来说，这段代码的主要部分如下：

1. 定义了一个大小为 N 的数组 cnt，用于记录每个整数出现的次数。
2. 进入一个 while 循环，当读入的 n 和 m 的和为 0 时跳出循环。在循环中，每次都需要先将数组 cnt 中的所有元素清零。
3. 使用 for 循环读入 m 个整数，并将它们记录在数组 cnt 中相应的位置上。即当读入整数 t 时，cnt[t] 的值加 1。
4. 再次使用 for 循环遍历数组 cnt，当某个元素的值大于 1 时，将计数器 res 的值加 1。
5. 最后将计数器 res 的值输出，并进行下一轮循环。

总的来说，这段代码实现了一个简单的统计算法，可以统计出在 m 个整数中出现次数大于 1 的整数的个数。

相关问题

#include <stdio.h> #include <string.h> #define N 10010 #define M 20010 int cnt[N]; //cnt[i],i出现的次数 int main(){ int n, m,t; while(scanf("%d%d", &n, &m), n + m){ memset(cnt, 0, sizeof(cnt)); int i, j, res = 0; for(i = 0; i < m; i++){ scanf("%d", &t); cnt[t]++; } for(i = 1; i <= n; i++){ if(cnt[i] > 1){ res ++; } } printf("%d\n", res); } return 0; }

这段代码的主要功能是读入两个整数 n 和 m，然后读入 m 个整数，统计这些整数中出现次数大于 1 的数的个数，并输出这个个数。

具体来说，该程序的主要步骤如下：

1. 定义了一个大小为 N 的数组 cnt，用于记录每个整数出现的次数。
2. 进入一个 while 循环，当读入的 n 和 m 的和为 0 时跳出循环。在循环中，每次都需要将数组 cnt 中的所有元素清零。
3. 使用 for 循环读入 m 个整数，并将它们记录在数组 cnt 中相应的位置上。即当读入整数 t 时，cnt[t] 的值加 1。
4. 再次使用 for 循环遍历数组 cnt，当某个元素的值大于 1 时，将计数器 res 的值加 1。
5. 最后将计数器 res 的值输出，并进行下一轮循环。

总的来说，该程序实现了一个简单的统计算法，可以统计出在 m 个整数中出现次数大于 1 的整数的个数。

#include<stdio.h> #include<math.h> int main() { int N,m; do{ scanf("%d",&N); }while(N<=1); printf("2 "); for(m=3;m<=N;m++){ int i; int tmp=(int)sqrt(m); for(i=2;i<=m;i++) if(m%i==0) break; if(i>tmp) printf("%d ",m); } return 0; } 优化该代码

上述代码是朴素的暴力枚举法，每次判断一个数是否为素数时都需要从2到该数的平方根进行循环，时间复杂度为O(n*sqrt(n))，效率较低。下面介绍两种优化方法：

1. 埃氏筛法优化

我们可以使用埃氏筛法来优化。具体做法是：首先定义一个长度为N+1的数组is_prime[]，其中is_prime[i]表示i是否是素数，初始时全部初始化为true。然后从2开始枚举每个素数i，将i的倍数j（j≥2且i*j≤n）标记为合数，即令is_prime[i*j]=false。最后输出所有is_prime[i]为true的i，即为小于等于n的所有素数。时间复杂度为O(n*loglog(n))，效率更高。

下面是优化后的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define MAXN 1000000

int main()
{
    int n;
    bool is_prime[MAXN + 1] = {false}; // 初始化为false
    scanf("%d", &n);

    printf("2 ");
    for (int i = 3; i <= n; i += 2) // 从3开始，每次加2
    {
        if (!is_prime[i])
        {
            printf("%d ", i);
            for (int j = i * i; j <= n; j += 2 * i) // 从i的平方开始标记，每次加2*i
            {
                is_prime[j] = true;
            }
        }
    }
    return 0;
}

2. 埃氏筛法进一步优化

在埃氏筛法的基础上，我们还可以进一步优化，减少时间和空间的使用。具体做法是：首先定义一个长度为N+1的数组is_prime[]，其中is_prime[i]表示i是否是素数，初始时全部初始化为true。然后从2开始枚举每个素数i，将i的倍数j（j≥2且i*j≤n）标记为合数，即令is_prime[i*j]=false。最后输出所有is_prime[i]为true的i，即为小于等于n的所有素数。

优化的关键在于：对于一个素数i，它的倍数2i、3i、4i、……已经被之前的素数标记过了，因此，在枚举素数i时，我们可以从i的平方开始标记，而不是从2i开始标记。这样可以减少一半的标记次数。

下面是优化后的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define MAXN 1000000

int main()
{
    int n, cnt = 0;
    bool is_prime[MAXN + 1] = {false}; // 初始化为false
    scanf("%d", &n);

    printf("2 ");
    for (int i = 3; i <= n; i += 2) // 从3开始，每次加2
    {
        if (!is_prime[i])
        {
            printf("%d ", i);
            cnt++;
            if (cnt % 10 == 0) // 每10个数换行
            {
                printf("\n");
            }
            for (int j = i * i; j <= n; j += 2 * i) // 从i的平方开始标记，每次加2*i
            {
                is_prime[j] = true;
            }
        }
    }
    return 0;
}