首页 > 试题广场 >

NowCoder小定律

[编程题]NowCoder小定律
  • 热度指数：4684 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<50),判定该表达式的值是否为素数

输入描述:
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。


输出描述:
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。
示例1

输入

0 1<br/>0 0

输出

OK
算法知识视频讲解
添加回答
啥头像 啥
总体思路：
        -39<=x<y<50,可以提前生成是否是素数的bool数组，然后判断

代码如下： 
#include <iostream>
#include <stdio.h>

using namespace std;

bool data[90];

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

int main()
{
    // 生成data数组
    for(int i=-39; i<50; i++) {
        data[i+39] = isPrime(i*i+i+41);
    }
    // 处理请求
    int x, y;
    while(~scanf("%d %d", &x, &y)) {
        if(x || y) {
            while(x<=y) {
                if(data[x+39]) {
                    x++;
                } else {
                    break;
                }
            }
            if(x>y) {
                printf("OK\n");
            } else {
                printf("Sorry\n");
            }
        } else {
            break;
        }
    }
    return 0;
}


发表于 2015-12-31 19:38:13 回复(0)
C/C++
hanjiangxue头像 hanjiangxue 
/*
 * 详解：https://blog.csdn.net/qq_33375598/article/details/104605488
 */
#include <cstdio>
(802)#include <cmath>

bool isPrime(int x){//判素数
    if(x <= 1) return false;
    int sqr = (int)sqrt(1.0 * x);
    for (int i = 2; i <= sqr; ++i) {
        if(x % i == 0) return false; 
    }
    return  true;
}

int main(int argc, char const *argv[]){
    int x, y;
    while(scanf("%d%d", &x, &y) != EOF){
        if(x == 0 && y == 0) break;

        bool isFound = true;//假定全部都是素数
        for (int i = x; i <= y; ++i) {
            int temp = i * i + i + 41;
            if(isPrime(temp) == false){
                isFound = false;
                break;
            }
        }
        if(isFound == true){
            printf("OK\n");
        }else{//有非素数的
            printf("Sorry\n");
        }
    }
    return 0;
}
发表于 2020-03-02 09:40:22 回复(1)
熊朝春头像 熊朝春 

	//keep simple and stupid，程序是给人看，容易看懂是很重要的；





	#include <stdio.h>





	#include <math.h>





	intIsPrime(intn);





	int main()





	{





	    int x, y, i;





	    scanf("%d %d", &x, &y);





	    while(x!=0||y!=0)





	    {





	        intflag=1;





	        for(i=x;i<=y;i++)





	        {





	            if(IsPrime(i*i+i+41)!=1)





	            {





	                printf("Sorry\n");





	                flag=0;





	                break;





	            }





	        }





	        if(flag==1)





	        {





	            printf("OK\n");





	        }





	        scanf("%d %d", &x, &y);





	    }





	    return0;  





	}





	int IsPrime(int n)





	{





	    int i, res=1;





	    if(n==1)





	    {





	        res=0;





	    }





	    else





	    {





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





	        {





	            if(n%i==0)





	            {





	                res=0;





	                break;





	            }





	        }





	    }





	    return res;





	}

发表于 2017-11-27 12:42:05 回复(0)
C/C++
一个好听的名字头像 一个好听的名字 
/*试探法。。。*/
#include <iostream>
using namespace std;
bool is_ok = true;
bool is_su(int n)
{
    bool right = true;
    int i = 2;
    for (; i < n; i++)
    {
        if (n % i == 0)
        {
            right = false;
            break;
        }
    }
    return right;
}
int main()
{
    int x = 0, y = 0;
    while (cin >> x >> y)
    {
        is_ok = true;
        if (x == 0 && y == 0)
        break;
        int i = x, j = 0, k = 0;
        for (; i <= y; i++)
        {
            if (!is_su(i * i + i + 41))
            {
                is_ok = false;
                break;
            }
        }
        if (is_ok)
        cout << "OK" << endl;
        else
        cout << "Sorry" << endl;
    }
}

发表于 2018-08-16 20:19:55 回复(0)
已注销头像 已注销 
#include<iostream>
#include<stdio.h>
using namespace std;

bool isPrime(int n){//判断素数
    if(n==1)
        return false;
    for(int i=2;i<n/2;i++)
        if(n%i==0)
            return false;
    return true;
}

int main()
{
    int x,y;
    while(~scanf("%d%d",&x,&y)){
        if(x-y==0){//特殊情况，输出空白
            cout<<endl;
            continue;
        }
            
        int flag=1;    //标记变量置为1
        for(int i=x;i<=y;i++){//从x到y遍历
            int z=i*i+i+41;
            if(!isPrime(abs(z))){//此时已经出现非素数
                flag=0;    //标记变量置为0，可以直接退出循环
                break;
            }
        }
        if(flag){
            cout<<"OK\n";
        }else{
            cout<<"Sorry\n";
        }
    }
    return 0;
}

发表于 2021-01-19 19:14:16 回复(0)
思晓头像 思晓 
#include <stdio.h>
 
int main()
{
    int x,y;
    while(1)
    {
        scanf("%d %d",&x,&y);
        if(x==y&&x==0)
            break;
        int flag=0;
        for(int i=x;i<=y;i++)
        {
            int n=i*i+i+41;
            for(int j=2;j*j<=n;j++)
            {
                if(n%j==0)
                {
                    printf("Sorry\n");
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
            continue;
        printf("OK\n");
    }
    return 0;
}
我真菜
发表于 2020-04-14 21:11:33 回复(0)
小黯头像 小黯 
#include<stdio.h>
int main()
{
	int i,j,k,m,x,y;
	while(scanf("%d %d",&x,&y)!=-1)
	{
		if(x!=0||y!=0)
		{
			k=1;
			for(i=x;i<=y;i++)
			{	
				m=i*i+i+41;
				for(j=2;j<m;j++)
					if(m%j==0)
						k=2;
			}
			if(k==1)
				printf("OK\n");
			else
				printf("Sorry\n");
		}
	}
	return 0;
}

发表于 2020-04-09 14:12:41 回复(0)
hestyle头像 hestyle 
#include <iostream>
(720)#include <math.h>
using namespace std;

// 判断number是否为素数
bool isPrimer(int number) {
    //判断在[1，sqrt(number)]是否存在因子
    for (int i = sqrt(number); i > 1; --i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

int main(int argc, const char * argv[]) {
    int a = 0, b = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d %d", &a, &b) != - 1) {
        //判断是否输入结束
        if (a == 0 && b == 0) {
            break;
        }
        //是否都是素数
        bool flag = true;
        //判断[a,b]进行i * i + i + 41后的结果是否都是素数
        for (int i = a; i <= b; ++i) {
            if (!isPrimer(i * i + i + 41)) {
                flag = false;
                break;
            }
        }
        printf((flag ? "OK\n" : "Sorry\n"));
    }
    return 0;
}

解题思路：
这题简单吧，写个判断素数的函数即可。
我这里是每次都判断[a,b]区间的所有值运算结果是否为素数，由于题目告诉了(-39<=x<50)条件，因此你也可以先建立一张表，用于记录各个值x运算结果是否为素数，判断区间[a,b]直接查表即可。

代码实现：\color{blue}代码实现：代码实现：


————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104648767
发表于 2020-03-04 10:52:41 回复(0)
C/C++
不偷不抢安度因_头像 不偷不抢安度因_ 
//终于换了一种题了哈，不是斐波那契数列了
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int is_prime(int n)
{
    if(n == 2)
        return 1;
    int m = sqrt(n);
    for(int i = 2; i <= m; i++)
    {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
 
int main()
{
    int x, y;
    int temp;
    while(1)
    {
        scanf("%d %d", &x, &y);
        if(x == 0 && y == 0)
            break;
        int target;
        temp = 1;
        for(int i = x; i <= y; i++)
        {
            target = i*i + i + 41;
            if(is_prime(target))
                continue;
            else
            {
                temp = 0;
                break;
            }
        }
        if(temp)
            printf("OK\n");
        else
            printf("Sorry\n");
    }
}

编辑于 2020-03-02 19:11:19 回复(0)
littlead头像 littlead
所以用了一下线段树
#include <iostream>
#include <cmath>
using namespace std;

struct TreeNode
{
    bool isPrime;
    short left;
    short right;
};

void buildTree(TreeNode *tree, short layer, short left, short right, bool *primes)
{
    tree[layer].left = left;
    tree[layer].right = right;

    if (left == right)
    {
        tree[layer].isPrime = primes[left];
        return;
    }

    short mid = (left + right) >> 1;
    buildTree(tree, 2 * layer, left, mid, primes);
    buildTree(tree, 2 * layer + 1, mid + 1, right, primes);

    tree[layer].isPrime = tree[2 * layer].isPrime & tree[2 * layer + 1].isPrime;
}

bool search(TreeNode *tree, short layer, short left, short right)
{
    if (tree[layer].right < left || tree[layer].left > right)
    {
        return true;
    }

    if (left <= tree[layer].left  && tree[layer].right <= right)
    {
        return tree[layer].isPrime;
    }

    bool isPrime = true;
    if (left <= tree[2 * layer].right)
    {
        //搜索左子树
        isPrime &= search(tree, 2 * layer, left, right);
    }
    
    if (right >= tree[2 *layer + 1].left)
    {
        //搜索右子树
        isPrime &= search(tree, 2 * layer + 1, left, right);
    }
    return isPrime;
}

bool isPrime(short n)
{
    if (n <= 2)
    {
        return true;
    }
    for (size_t i = 2; i <= sqrt(n) ; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    bool primes[91];
    for (size_t i = 1; i < 91; i++)
    {
        short n = (i - 40) * (i - 40) + i + 1;
        primes[i] = isPrime(n);
    }
    TreeNode tree[90 * 4];
    buildTree(tree, 1, 1, 90, primes);

    short x, y;
    cin >> x >> y;
    while (x != 0 || y != 0)
    {
        if (search(tree, 1, x + 40, y + 40))
        {
            cout << "OK" << endl;
        }
        else
        {
            cout << "Sorry" << endl;
        }
        cin >> x >> y;
    }
    return 0;
}
发表于 2019-09-21 16:25:10 回复(0)
疯子cjx头像 疯子cjx
#include <bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
    if(n<2) return false;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0) return false;
    }
    return true;
}
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        int flag=1;
        if(a==b&&a==0)
            break;
        for(int i=a;i<=b;i++)
        {
            if(!isprime(i*i+i+41))
            {
                cout<<"Sorry"<<endl;
                flag=0;
                break;
            }
        }
        if(flag)
        {
            cout<<"OK"<<endl;
        }
    }
}

发表于 2019-08-23 21:47:53 回复(0)
JCChan头像 JCChan 
#include<iostream>
using namespace std;

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

int main() {
	int x;
	int y;
	while (cin >> x >> skipws >> y) {
		if (x == 0 && y == 0) {
			break;
		}
		else {
			int i = x;
			for (; i <= y; i=i++) {
				if (!isPrime(i*i+i+41)) {
					cout << "Sorry" << endl;
					break;
				}
			}
			if (i == y + 1) {
				cout << "OK" << endl;
			}
		}
	}
	return 0;
}

完全不知道这都能超时.......


发表于 2019-07-07 20:41:33 回复(0)
千手、修罗头像 千手、修罗
/**
* Copyright(c)
* All rights reserved.
* Author : ZhengChang
* Link : https://github.com/ZhengChang467
* Mail : changzheng18z@ict.ac.cn
* Date : 2019-04-08-14.29.15
* Description : https://www.nowcoder.com/pat/2/problem/259
*/
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include <stdlib.h>
using namespace std;
bool is_prime(int n)
{
    for(int i=2; i<n; i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int x,y;
    while(scanf("%d %d",&x,&y))
    {
        int flag = 1;
        if(x==0&&y==0)
            break;
        else
        {
            for(int i=x; i<=y; i++)
            {
                if(!is_prime(i*i+i+41))
                {
                    flag = 0;
                    break;
                }
            }
        }
        if(flag)
            printf("OK\n");
        else
            printf("Sorry\n");
    }
    return 0;
}

发表于 2019-04-08 15:03:02 回复(0)
C/C++
romanten头像 romanten
//1011.NowCoder小定律
#include <cstdio>
#include <cmath>
int main()
{
    int x,y,f=1;
    while(~scanf("%d%d",&x,&y)){
        if(x==0&&y==0) break;
        f=1;
        for(int i=x;i<=y;++i){
            if(f==0) break;
            int t=i*i+i+41;
            for(int j=2;j<=sqrt(t);j++){
                if(t%j==0){
                    f=0;
                    break;
                }
            }
        }
        if(f==1) printf("OK\n");
        else printf("Sorry\n");
    }
    return 0;
}
发表于 2019-01-12 20:47:08 回复(0)
Disconnect头像 Disconnect 
def math(m):
    tem = m*m+m+41
    t = int(pow(tem,0.5))
    for j in range(2,t+1):
        if tem%j==0:
            return False
    return True
def domath(a,b):
    for n in range(a,b+1):
        if math(n)==False:
            return False
    return True 

try:
    while True:
        x,y = map(int,input().split())
        if x==0 and y==0:
            break
        if domath(x,y):
            print("OK")
        else:
            print("Sorry")
except:
    pass

发表于 2018-11-29 13:34:10 回复(1)
SupritYoung头像 SupritYoung
详细题解
发表于 2018-11-12 20:54:26 回复(0)
ShouldBeOk头像 ShouldBeOk
/*
 * =====================================================================================
 *
 *       Filename:  11NowCoder小定律.cpp
 *
 *        Version:  1.0
 *        Created:  2018/09/24 13:14:10
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Covfefe
 *   Organization:    Fs-studio
 *   
 *             idea:           n:    0    1    2    3    4    5    6    7    -1    -2    -3    -4    ……
 *                    n^2+n+41:    41    43    47    53    61    71    83    97    41    43    47    53    ……都是素数
 *                    化简表达式n(n+1)+41, n=40时值为41^2；n=41时值为41*43。此时值不是素数。
 *
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
#define FOR(i,n) for(i = 2; i < n; i++)
bool isSushu(int n)
{
    int i, val = n * n + n + 41;
    FOR(i, (int)sqrt(val) + 1)
        if (val % i != 0)
            continue;
        else
            break;
    if (i != (int)sqrt(val) + 1)
        return false;
    else
        return true;
}

int main()
{
    int x, y, i, j;
    bool sushuFlag[52] = {false};
    for (i = 0; i < 50; i++)
    {
        sushuFlag[i] = isSushu(i);
    }
    cin >> x >> y;
    while (x != 0 || y != 0)
    {
        for (i = x; i <= y; i++)
        {
            j = i < 0 ? -1 - i : i;
            if (!sushuFlag[j])
                break;
        }
        printf((i == y + 1 ? "OK\n" : "Sorry\n"));
        cin >> x >> y;
    }
    return 0;
}
发表于 2018-09-24 14:27:29 回复(0)
C/C++
Caffeine头像 Caffeine 
思路：素数的列表法，就是任何合数都可以表示成几个素数，然后标记一下，谁是素数的倍数，然后就可以了
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
vector<long long> v(100001);
#define N 100000
void init() {
    int i, j;
    for (i = 2; i <= N; i++) {
        v[i] = 1;
    }
    for (i = 2; i <= N; i++) {
        //if (v[i]) printf(" %d ", i);
        for (j = i + i; j <= N; j += i) v[j] = 0;
    }
}

int main()
{
    int x, y;

    init();


    while (cin >> x >> y)
    {
        if (x == 0 && y == 0)
        {
            continue;
        }
        int temp;
        bool decide = false;
        for (int i = x; i <= y; i++)
        {
            temp = i * i + i + 41;
            if (v[temp] == 0)
            {
                decide = true;
                cout << "Sorry" << endl;
                break;
            }
        }
        if (!decide)
            cout << "OK" << endl;
    }
}

发表于 2018-08-12 09:21:55 回复(0)
C/C++
这菜都齐了怎么还不吃啊头像 这菜都齐了怎么还不吃啊 
//埃式筛选法

#include <bits/stdc++.h>
#define PI 3.1415927
using namespace std; 
typedef  long long ll;
ll arr[1000005];
//1 2 3 5

bool isp[2600];
void init()
{     fill (isp,isp+2600,true);     isp[0]=isp[1]=false;     for(int i=0;i<=2591;i++)     {         if(isp[i])         {             for(int j=i*2;j<=2591;j+=i)                  isp[j]=false;         }     }      }
int main(void)  
{        init();     ios::sync_with_stdio(false);     cin.tie(0);         int x,y;     while(cin>>x>>y)     {         if(x==0&&y==0)             break;         else         {             int ans=0;             for(int i=x;i<=y;i++)             {                 if(isp[i*i+i+41])                     ans++;             }             if(ans==y-x+1)                 cout<<"OK"<<endl;             else                 cout<<"Sorry"<<endl;         }     }              return 0;
}  

发表于 2018-08-01 20:46:36 回复(0)
CodeTiger头像 CodeTiger 
#include<stdio.h>
#include<math.h>
int isPrime(int n)
{
    int i;
    int flag = 1;
    if(n == 1)
    {
        flag = 0;
    }
    for(i = 2; i <= (int)sqrt(n); i++)
    {
        if(n % i == 0)
        {
            flag = 0;
        }
    }
    return flag;
}
int main(void)
{
    int a;
    int b;
    int i;
    int flag = 1;
    while(~scanf("%d%d", &a, &b))
    {
        if(a == 0 && b == 0)
        {
            break;
        }
        for(i = a; i <= b; i++)
        {
            if(isPrime(i * i + i + 41) == 0)
            {
                flag = 0;
                break;
            }
        }
        if(flag == 1)
        {
            printf("OK\n");
        }
        else
        {
            printf("Sorry\n");
        }         flag = 1;
    }
}

发表于 2018-04-01 16:42:46 回复(0)
提交观点

问题信息

难度：
31条回答 8702浏览

热门推荐

通过挑战的用户

相关试题

NowCoder小定律

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号