计算机数学2: 数论

ID: 9831

客观题

尝试: 3

已通过: 0

难度: 10

上传者:

bitworld

标签>

CSP

初赛

1.单选题 [NOIP普及组2017/NOIP提高组2017] 2017年10月1日是星期日，1999年10月1日是( )。 {{ select(1) }}

星期三
星期日
星期五
星期二

2.单选题 [GESP202312【1级】] 假设现在是上午十点，求出N小时（正整数）后是第几天几时，如输入20小时则为第2天6点，如N输入4则为今天14点。为实现相应功能，应在横线处填写代码是( )。

int N, dayX,hourX;
    cin >>N;
    dayX =_____,hourX =_______;
    if (dayX ==0)
        cout<<"今天"<<hourX <<"点";
    else
        cout<<"第"<<(dayX+1)<<"天"<<hourX <<"点";

(10 + N) % 24 , (10 + N) / 24
(10 + N) / 24 , (10 + N) % 24
N % 24 , N / 24
10 / 24 , 10 % 24

3.单选题 [CSP-J2020] 干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。天干 =（公历年份）除以10所得余数地支 =（公历年份）除以12所得余数例如，今年是2020年，2020除以10余数为0，查表为"庚"；2020除以12，余数为4，查表为"子"所以今年是庚子年。请问1949年的天干地支是（）

己酉
己亥
己丑
己卯

4.单选题 [NOIP普及组2016] 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D、......，屏幕上输出的第81个字符是字母( )。 {{ select(4) }}

5.单选题 [NOIP提高组2016] 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序来回按键，即CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、......，屏幕上输出的第81个字符是字母（）。 {{ select(5) }}

6.单选题 [NOIP普及组2018] 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第81个字符是字母（）。 {{ select(6) }}

7.填空题 [NOIP提高组2007] N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。则J(400)=______________。（提示：对N=2^m+r进行分析，其中0≤r<2^m）。 {{ input(7) }}

8.填空题 [NOIP普及组2017] 一个人站在坐标（0，0）处，面朝x轴正方向。第一轮，他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位距离，然后右转......他一直这么走下去。请问第2017轮后，他的坐标是：（___ , ___）。

9.单选题 [GESP202403【2级】] 下面C++代码执行后的输出是（）。

int n,masks,days,cur;
n=17,masks=10,day=0;
cur=2;
while(masks!=n){
    if(cur==0||cur==1)
        masks+=7;
    masks-=1;
    days+=1;
    cur=(cur+1)%7;
}

11.填空题 [NOIP提高组2004]

#include <stdio.h>
const int u[3]={1,-3,2};
const int v[2]={-2,3};
int g(int n){
    int i,sum =0;
    for(i=1;i<=n;i++)
        sum += u[i % 3]* i;
    return sum;
}
int main(){
    int n,i,sum =0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        sum += v[i% 2]* g(i);
    printf("%d\n",sum);
    return 0;
}

输入：103 输出： {{ input(11) }}

12.填空题 [NOIP普及组2015] （打印月历）输入月份m(1≤m≤12)，按一定格式打印2015第m月的月历。例如，2015年一月的月历打印效果如下（第一列为周日）：

#include<iostream>
using namespace std;
const int dayNum[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};
int m, offset, i;
int main()
{
    cin >> m;
    cout <<"S    M   T   W   T   F   S"<<endl;//'  '为tab制表符
    ①;
    for (i = 1; i < m; i++)
        offset = ②;
    for (i = 0; i < offset; i++)
        cout <<' ';
    for (i = 1; i <= ③;i++)
    {
        cout << ④;
        if(i==dayNum[m]||⑤==0)
            cout << endl;
        else
            cout << '   ';
    }
    return 0;
}

13.填空题 [NOIP普及组2004/NOIP提高组2004] Joseph 题目描述: 原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。输入:仅有的一个数字是k（0 < k <14）。输出:使得最先出列的k个人都是坏人的m的最小值。输入样例:4 输出样例:30 程序：

#include <stdio.h>
long k, m, begin;
int check(long remain){
    long result = (  ①  ) % remain;
    if (  ②  ){
        begin = result; return 1;
    }
    else return 0;
}
int main(){
    long i, find = 0;
    scanf("%ld", &k);
    m = k;
    while(  ③  ) {
        find = 1; begin = 0;
        for (i = 0; i < k; i++)
            if (!check(  ④  )){
                find = 0; break;
            }
        m++;
    }
    printf("%ld\n",   ⑤  );
    return 0;
}

15.填空题 [NOIP普及组2009]

#include <stdio.h>
int main()
{
    int a[3],b[3];
    int i,j,tmp;
    for (i=0;i<3;i++)
    scanf("%d",&b[i]);
    for (i=0;i<3;i++)
    {
        a[i]=0; 
        for (j=0;j<=i;j++)
        {
            a[i]+=b[j];
            b[a[i]%3]+=a[j];
        }
    }
    tmp=1;
    for (i=0;i<3;i++)
    {
        a[i]%=10;
        b[i]%=10;
        tmp*=a[i]+b[i];
    }
    printf("%d\n",tmp);
    return 0;
}

输入：2 3 5 输出：_______ {{ input(15) }}

16.填空题 [NOIP提高组2009]

#include <iostream>
using namespace std;
int main()
{
    int a[4],b[4];
    int i,j,tmp;
    for (i=0;i<4;i++)
    cin >> b[i];
    for (i=0;i<4;i++) 
    {
        a[i]=0;
        for (j=0;j<=i;j++)
        {
            a[i]+=b[j;
            b[a[i]%4]+=a[j];
        }
    }
    tmp=1;
    for (i=0;i<4;i++) 
    {
        a[i]%=10;
        b[i]%=10;
        tmp*=a[i]+b[i];
    }
    cout << tmp << endl;
    return 0;
}

输入：2 3 5 7 输出：_________ {{ input(16) }}

17.多选题 [GESP202312【5级】/GESP202312【6级】] 小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。 {{ multiselect(17) }}

正确
错误

18.单选题 [GESP202309【1级】/GESP202312【2级】] 下面C++代码用于求正整数的所有因数，即输出所有能整除一个正整数的数。如，输入10，则输出为1、2、5、10；输入12，则输出为1、2、3、4、6、12；输入17，则输出为1、17。在横线处应填入代码是（）。

int n=0:
cout<<"请输入一个正整数:";
cin >>n;
for(______)//此处填写代码
    if(n %i == 0)
        cout << i<< endl;

int i = 1; i < n; i + 1
int i = 1; i < n + 1; i + 1
int i = 1; i < n; i++
int i = 1; i < n + 1; i++

19.单选题 [GESP202309【2级】] 以下C++代码实现从大到小的顺序输出N的所有因子。例如，输入N=18时输出1896321，横线处应填入（）。

int N=0;
cin>>N;
for(_______)//此处填写代码
    if(!(N%i))
        cout<<i<<' ';

; ;
int i=1;i<N;i++
int i=N;i>0;i--
int i=N;i>1;i--

20.单选题 [GESP202312【4级】] 以下C++代码用于实现每个整数对应的因数，如输入12，则输出1234612；如输入18，则输出1236918。横线处应填入代码是

int n:
cin>>n;
for(int i=1;i<=n;i++){
    _______//此处填写代码
        cout<<i<<endl;
}

if(n%i==0)
if(n/i==0)
if(n%i!=0)
if(n/i!=0)

21.单选题 [GESP202312【2级】/GESP202312【4级】] 输入一个正整数N，想找出它所有相邻的因数对，比如，输入12，因数对有(1,2)、(2,3)、(3,4)。下面哪段代码找不到所有的因数对？（） {{ select(21) }}

for(i=1;i<N;i++) if(!(N%i) && !(N%(i+1))) printf("(%d,%d)\n",i,i+1);
for(i=2;i<N;i++) if(!(N%i) && !(N%(i+1))) printf("(%d,%d)\n",i,i+1);
for(i=2;i<N/2;i++) if(!(N%(i-1)) && !(N%i)) printf("(%d,%d)\n",i-1,i);
for(i=1;i<N/2;i++) if(!(N%i) && !(N%(i+1))) printf("(%d,%d)\n",i,i+1);

24.单选题 [CSP-J2019] 319和377的最大公约数是（）。 {{ select(24) }}

25.单选题 [GESP202403【5级】] 辗转相除法也被称为（） {{ select(25) }}

高斯消元法
费马定理
欧几里德算法
牛顿迭代法

26.多选题 [GESP202403【5级】] 辗转相除法用于求两个整数的最大公约数。 {{ multiselect(26) }}

正确
错误

27.单选题 [GESP202406【5级】] 下面是根据欧几里得算法编写的函数，它计算的是与的（）。

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

最小公倍数
最大公共质因数
最大公约数
最小公共质因数

28.单选题 [GESP样题【5级】/NOIP普及组2013] 下列代码中，函数f的作用是（）。

void f(int a, int b){
    return b==0? a:f(b, a % b);
}

求a和b的最大公共质因子
求a和b的最小公共质因子
求a和b的最大公约数
求a和b的最小公倍数

29.单选题 [GESP202406【5级】] 欧几里得算法还可以写成如下形式:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

下面有关说法，错误的是（）。 {{ select(29) }}

本题的gcd()实现为递归方式
本题的gcd()代码量少，更容易理解其辗转相除的思想
当较⼤时，本题的gcd()实现会多次调用自身，需要较多额外的辅助空间
当较⼤时，相比上题中的gcd()的实现，本题的gcd()执行效率更高

30.单选题 [GESP202403【6级】] 以下代码使用了辗转相除法求解最大公因数，请在横线处填入（），使其能正确实现相应功能。

int gcd(int a,int b){
    while(b!=0){
        __________;
    }
    return a;
}

int temp = b; b = a / b; a = temp;
int temp = a; a = b / a; b = temp;
int temp = b; b = a % b; a = temp;
b = a % b; a = b;

31.单选题 [GESP202312【5级】] 有关下面C++代码说法正确的是（）。

int rc;
int foo(int x, int y)
{
    int r;
    if (y == 0)
        r = x;
    else
    {
        r = foo(y, x % y);
        rc++;
    }
    return r;
}

如果x小于10，rc值也不会超过20
foo可能无限递归
foo可以求出x和y的最大公共质因子
foo能够求出x和y的最小公倍数

32.填空题 [NOIP普及组2009]

#include <iostream>
using namespace std;
int a, b;
int work(int a, int b) {
    if (a % b)
        return work(b, a % b);
    return b;
}
int main() {
    cin >> a >> b;
    cout << work(a, b) << endl;
    return 0;
}

输入：20 12 输出：_______ {{ input(32) }}

33.填空题 [NOIP提高组2009]

#include <iostream>
using namespace std;
int a, b;
int work(int a, int b) {
    if (a % b)
        return work(b, a % b);
    return b;
}
int main() {
    cin >> a >> b;
    cout << work(a, b) << endl;
    return 0;
}

输入：123 321 输出：_______ {{ input(33) }}

34.填空题 [NOIP提高组2012]

#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b){
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
int main(){
    cin>>n;
    ans = 0;
    for (i = 1;i <= n;i++)
        if (gcd(n,i) == i)ans++;
    cout<<ans<<endl;
}

输入：120 输出：____ {{ input(34) }}

35.单选题 [GESP202312【8级】] 假设输入参数 m 和 n 满足，则下面程序的最差情况的时间复杂度为（）。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

O(log(n))
O(n)
O(n*m)
O(m*log(n))

36.填空题 [NOIP普及组2018] （最大公约数之和）下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对10007 求余后的值，试补全程序。举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约数为 2；1 和 4 的最大公约数为 1。于是答案为 1 + 2 + 1 = 4。要求 getDivisor 函数的复杂度为 O(√n)，gcd 函数的复杂度为O(log max(a,b))。

#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
    len = 0;
    for (int i = 1; ① <= n; ++i)
        if (n % i == 0) {
            a[++len] = i;
            if ( ② != i) a[++len] = n / i;
        }
    }
}
int gcd(int a, int b) {
    if (b == 0) {
        ③ ;
    }
    return gcd(b, ④ );
}
int main() {
    cin >> n;
    getDivisor();
    ans = 0;
    for (int i = 1; i <= len; ++i) {
        for (int j = i + 1; j <= len; ++j) {
            ans = ( ⑤ ) % P;
        }
    }
    cout << ans << endl;
    return 0;
}

37.单选题 [GESP202406【8级】] 下面程序的最差时间复杂度为（）。

int gcd(int m, int n) { 
    if (m == 0) return n; 
    return gcd(n % m, m); 
}

O(SQRT(n))
O(log(n))
O(n)
O(1)

38.单选题 [CSP-J2019] 100 以内最大的素数是（）。 {{ select(38) }}

39.单选题 [NOIP普及组2018] 10000 以内，与10000 互质的正整数有（）个。 {{ select(39) }}

2000
4000
6000
8000

40.单选题 [GESP202403【5级】] 唯一分解定理描述的内容是（）？ {{ select(40) }}

任意整数都可以分解为素数的乘积
每个合数都可以唯一分解为一系列素数的乘积
两个不同的整数可以分解为相同的素数乘积
以上都不对

41.单选题 [GESP样题【5级】/GESP样题【6级】] 唯一分解定理指的是分解质因数只有唯一的一种算法。 {{ select(41) }}

正确
错误

42.单选题 [GESP202312【5级】] 小杨设计了一个拆数程序，它能够将任意的非质数自然数N转换成若干个质数的乘积，这个程序是可以设计出来的。 {{ select(42) }}

正确
错误

43.单选题[GESP202406【7级】] 唯一分解定理（算术基本定理）指出，每个大于1的自然数都可以唯一地分解成若干个素数的乘积。因此，我们可以很容易的对给定的自然数 n 进行质因数分解，时间复杂度仅为 O(n)。 {{ select(43) }}

正确
错误

44.单选题 [GESP202406【5级】] 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。 {{ select(44) }}

正确
错误

45.单选题 [GESP样题【6级】] 现希望存储整数N的所有质因子，请问其空间复杂度上界为是（）。 {{ select(45) }}

O(loglogN)
O(logN)
O(√N)
O(N)

46.填空题 [CSP-J2020] 这个题没有选项，自己把整个程序写出来吧在纸上（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤10^9。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。试补全程序。

#include <cstdio>
using namespace std;
int n, i;
int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

47.单选题 [GESP202403【5级】] 下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（）

bool isPrime(int num){
    if(num<2){
        return false;
    }
    for(int i=2;i*i<num; ++i)
            if(num%i==0){
                return false;
            }
    return true;
}

num < 2 应该改为 num <= 2
循环条件 i * i < num 应该改为 i * i <= num
循环条件应该是 i <= num
循环体中应该是 if (num % i != 0)

48.单选题 [GESP202303【2级】] 执行以下 C++语言程序后，输出结果是（）。

#include <iostream>
using namespace std;
int main(){
    int n = 17;
    bool isprime =true;
    for(int i=2;i<= n; i++)
        if(n%i==0)
            isprime = false;
    cout<< isprime<< endl;
    return 0;
}

false
true
0
1

49.单选题 [GESP202403【1级】] 下面C++代码用于判断键盘输入的整数是否为质数。质数是只能被1和它本身整除的数。在横线处应填入代码是（）。

int N;
cin >>N;
int cnt =0;//记录N被整除的次数
for(int i=1; i<N+1; i++)
    if(_______)
        cnt +=1;
if(cnt == 2)
    cout<<"是质数";
else
    cout<<"不是质数";

N % i
N % i == 0
N / i == 0
N / i

50.单选题 [GESP202312【1级】] 下面C++代码用于判断一个数是否为质数（素数），在横线处应填入代码是（）。

cin >>N;
int cnt =0;//记录N被整除的次数
for(int i=1; i<N+1; i++)
    if(N%i==0)
        ________;
if(cnt == 2)
    cout<<"是质数";
else
    cout<<"不是质数";

cnt = 1
cnt = 2
cnt =+ 1
cnt += 1

51.单选题 [GESP202309【2级】] 下面C++代码用于判断 N 是否为质数（素数），约定输入 N 为大于等于2的正整数，请在横线处填入合适的代码（）。

int N=0,i=0;
cout<<"请输入一个大于等于2的正整数:";
cin >>N;
for(i=2;i<N;i++)
    if(N%i== 0){
        cout<<"非质数";
        _______;//此处填写代码
    }
if(i == N)
    cout<<"是质数";

break
continue
exit
return

52.单选题 [GESP202312【2级】] 下面C++代码用于判断N（大于等于2的正整数）是否为质数（素数）。下面对如下代码的说法，正确的是（）。

cin>>N;
for(i = 2;i < N/2; i++)
    if(N %i ==0){
        cout<<N<<"不是质数";
        break;
    }
if(i>= N/2)
    cout<<N<<"是质数";

代码能正确判断N是否为质数
代码总是不能判断N是否质数
删除第5行 break，将能正确判断N是否质数
代码存在漏洞，边界存在问题，应将第2行和第7行的 N / 2 改为 N / 2 + 1

53.单选题 [GESP202312【5级】] 下面C++代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数N是否素数，有关其时间复杂度的正确说法是（）。

bool isPrimeA(int N) {
    if(N<2) return false;
    for(int i=2;i<=N/2;i++)
        if(N%i==0) return false;
    return true;
}

bool isPrimeB(int N){
    if(N<2) return false;
    for(int i=2;i<=sqrt(N);i++)
        if(N%i==0) return false;
    return true;
}

isPrimeA()的最坏时间复杂度是O(N/2)，isPrimeB()的最坏时间复杂度是O(logN)，isPrimeA()优于isPrimeB()
isPrimeA()的最坏时间复杂度是O(N/2)，isPrimeB()的最坏时间复杂度是O(N^0.5)，isPrimeB()绝大多数情况下优于isPrimeA()
isPrimeA()的最坏时间复杂度是O(N^0.5)，isPrimeB()的最坏时间复杂度是O(N)，isPrimeA()优于isPrimeB()
isPrimeA()的最坏时间复杂度是O(logN)，isPrimeB()的最坏时间复杂度是O(N)，isPrimeA()优于isPrimeB()

54.单选题 [GESP202309【5级】] 下面代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 N 是否素数，有关其时间复杂度的正确说法是（）。

#include <iostream>
#include <cmath>
using namespace std;
bool isPrimeA(int N) {
    if (N < 2) return false;
    for (int i = 2; i < N; i++) {
        if (N % i == 0) return false;
    }
    return true;
}

bool isPrimeB(int N) {
    if (N < 2) return false;
    int endNum = int(sqrt(N));
    for (int i = 2; i <= endNum; i++) {
        if (N % i == 0) return false;
    }
    return true;
}

isPrimeA()的最坏时间复杂度是O(N)，isPrimeB()的最坏时间复杂度是O(logN)，isPrimeB()优于isPrimeA()
isPrimeA()的最坏时间复杂度是O(N)，isPrimeB()的最坏时间复杂度是O(N^0.5)，isPrimeB()优于isPrimeA()
isPrimeA()的最坏时间复杂度是O(N^0.5)，isPrimeB()的最坏时间复杂度是O(N)，isPrimeA()优于isPrimeB()
isPrimeA()的最坏时间复杂度是O(logN)，isPrimeB()的最坏时间复杂度是O(N)，isPrimeA()优于isPrimeB()

55.填空题 [NOIP普及组2010] （哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。试补全程序：

#include<iostream>
using namespace std;
int main() {
    const int SIZE = 1000;
    int n, r, p[SIZE], i, j, k, ans;
    bool tmp;
    cin>>n;
    r = 1;
    p[1] = 2;
    for (i = 3; i <= n; i++) {
        ①_______;
        for (j = 1; j <= r; j++)
            if (i % ②______) {
                tmp = false;
                break;
            }
        if (tmp) {
            r++;
            ③_________ 
        }
    }
    ans = 0;
    for (i = 2; i <= n / 2; i++) {
        tmp = false;
        for (j = 1; j <= r; j++)
            for (k = j; k <= r; k++)
                if (i + i == ④_______) {
                    tmp = true;
                    break;
                }
        if (tmp) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

若输入n为2010，则输出⑤_______时表示验证成功。 {{ input(55) }}

56.填空题 [NOIP普及组2005] 判断质数

#include <stdio.h>
int main() {
    int ①; 
    scanf("%d", &n);
    if (n == 2) puts(②); 
    else if (③ || n % 2 == 0) puts("NO"); 
    else {
        i = 3;
        while (i * i <= n) {
            if (④) { 
                puts("NO");
                return 0;
            }
            i = i + 2;
        }
        puts("YES");
    }
    return 0;
}

57.单选题 [GESP202406【1级】] 下面C++代码用于判断N是否为质数（只能被1和它本身整除的正整数）。程序执行后，下面有关描述正确的是（）。

int N;
cout << "请输入整数：";
cin >> N;
bool Flag = false;
if (N >= 2) {
    Flag = true;
    for (int i = 2; i < N; i++) {
        if (N % i == 0) {
            Flag = false;
            break;
        }
    }
}
if (Flag)
    cout << "是质数";
else
    cout << "不是质数";

如果输入负整数，可能输出"是质数"
如果输入2，将输出"不是质数"，因为此时循环不起作用
如果输入2，将输出"是质数"，即便此时循环体没有被执行
如果将if(N >= 2)改为if(N > 2)将能正确判断N是否质数

58.单选题 [GESP202406【2级】] 执行下面的C++代码，有关说法正确的是（）【质数是指仅能被1和它本身整除的正整数】。

int N;
cin >> N;
bool Flag = true;
for (int i = 2; i < N; i++) {
    if (i * i > N) break;
    if (N % i == 0) {
        Flag = false;
        break;
    }
}
if (Flag)
    cout << N << "是质数" << endl;
else
    cout << N << "不是质数" << endl;

如果输入正整数，上面代码能正确判断N是否为质数
如果输入整数，上面代码能正确判断N是否为质数
如果输入大于等于0的整数，上面代码能正确判断N是否质数
如将Flag = true修改为Flag = N>=2? true:false则能判断所有整数包括负整数、0、正整数是否为质数

59.判断题 [GESP样题【6级】/GESP202309【5级】] 质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。 {{ select(59) }}

正确
错误

60.判断题 [GESP202309【5级】] 找出自然数N以内的所有质数，常用算法有埃氏筛法和线性筛法，其中埃氏筛法效率更高。 {{ select(60) }}

正确
错误

61.单选题 [GESP202403【6级】] 线性筛法与埃氏筛法相比的优势是（）。 {{ select(61) }}

更容易实现
更节省内存
更快速
更准确

62.单选题 [GESP202312【5级】/GESP202312【6级】] 小杨想编写一个判断任意输入的整数N是否为素数的程序，下面哪个方法不合适？（） {{ select(62) }}

埃氏筛法
线性筛法
二分答案
枚举法

63.判断题 [GESP样题【5级】] 埃氏筛法用于找出自然数N以内的所有质数，其时间复杂度为O(N*sqrt(N))，因为判定一个数是否为质数的时间复杂度为O(N)。 {{ select(63) }}

正确
错误

64.判断题 [GESP202403【5级】] 素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN)。 {{ select(64) }}

正确
错误

65.判断题 [GESP202406【5级】] 找出自然数n以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。 {{ select(65) }}

正确
错误

66.单选题 [GESP202403【5级】] 素数的线性筛法时间复杂度为（）。 {{ select(66) }}

O(n)
O(nloglogn)
O(nlogn)
O(n^2)

67.单选题 [GESP202403【8级】] 下面程序的时间复杂度为（）。

int primes[MAXP],num=0;
bool isPrime[MAXN]={false};
void sieve(){
    for(int n=2;n<=MAXN;n++){
        if(!isPrime[n])
            primes[num++]=n;
        for(int i=0;i<num&&n*primes[i]<=MAXN;i++){
            isPrime[n*primes[i]]=true;
            if(n%primes[i]==0) break;
        }
    }
}

O(n)
O(n*logn)
O(n*loglogn)
O(n^2)

68.单选题 [GESP202403【5级】] 在埃拉托斯特尼筛法中，要筛选出不大于n的所有素数，最外层循环应该遍历什么范围（）？

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    _______________{
        if(isPrime[i]){
            primes.push_back(i);
            for(int j=i*i;j<=n;j+=i)
                isPrime[j]=false;
        }
    }
    for(int i=sqrt(n)+1;i<=n;i++)
        if(isPrime[i]) primes.push_back(i);
    return primes;
}

for(int i=2;i<=n;++i)
for(int i=1;i<n;++i)
for(int i=2;i<=sqrt(n);++i)
for(int i=1;i<=sqrt(n);++i)

69.填空题 [NOIP普及组2007]

#include <iostream.h>
#include <iomanip.h>
#include "math.h"
void main() {
    int a1[51]={0};
    int i,j,t,t2,n=50;
    for(i=2;i<=sqrt(n);i++)
        if(a1[i]==0){
            t2=n/i;
            for(j=2;j<=t2;j++) a1[i*j]=1;
        }
    t=0;
    for(i=2;i<=n;i++)
        if(a1[i]==0){
            cout<<setw(4)<<i; t++;
            if(t%10==0) cout<<endl;
        }
    cout<<endl;
}

输出：_______________________________ {{ input(69) }}

70.填空题 [NOIP提高组2007]

#include <iostream.h>
#include <iomanip.h>
#include "math.h"
void main() {
    int a1[51]={0};
    int i,j,t,t2,n=50;
    for(i=2;i<=sqrt(n);i++)
        if(a1[i]==0){
            t2=n/i;
            for(j=2;j<=t2;j++) a1[i*j]=1;
        }
    t=0;
    for(i=2;i<=n;i++)
        if(a1[i]==0){
            cout<<setw(4)<<i; t++;
            if(t%10==0) cout<<endl;
        }
    cout<<endl;
}

输出：_______________________________ {{ input(70) }}

71.填空题 [NOIP提高组2018]

#include <cstdio>
int n,d[100];
bool v[100];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",d+i);
        v[i]=false;
    }
    int cnt=0;
    for(int i=0;i<n;++i){
        if(!v[i]){
            for(int j=i;!v[j];j=d[j])
                v[j]=true;
            ++cnt;
        }
    }
    printf("%d",cnt);
    return 0;
}

输入：10 7 1 4 3 2 5 9 8 0 6 输出：（） {{ input(71) }}

74.填空题 [NOIP普及组2014]

#include <iostream>
using namespace std;
const int SIZE = 100;
int main() {
    int p[SIZE];
    int n, tot, i, cn;
    tot = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        p[i] = 1;
    for (i = 2; i <= n; i++) {
        if (p[i] == 1)
            tot++;
        cn = i * 2;
        while (cn <= n) {
            p[cn] = 0;
            cn += i;
        }
    }
    cout << tot << endl;
    return 0;
}

输入：30 输出：___ {{ input(74) }}

75.单选题 [GESP202406【5级】] 下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是（）。

vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        ____________________________ {
            is_prime[i * primes[j]] = 0;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
for (int j = 0; j <= n; j++)
for (int j = 1; j <= sqrt(n); j++)

76.单选题 [GESP202406【5级】] 下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，时间复杂度是（）。

vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 0;
        }
        if (i % primes[j] == 0)
            break;
    }
    return primes;
}

O(n^2)
O(nlogn)
O(nloglogn)
O(n)

77.单选题 [GESP202406【8级】] 下面程序的时间复杂度为（）。

bool notPrime[N] = {false};
void sieve() {
    for (int n = 2; n * n < N; n++)
        if (!notPrime[n])
            for (int i = n * n; i < N; i += n)
                notPrime[i] = true;
}

O(N)
O(NlogN)
O(NloglogN)
O(N^2)

#CSPJKG52. 计算机数学2: 数论

还没有账户？

登录