玄学RE,求助
查看原帖
玄学RE,求助
342388
卧槽楼主2020/5/11 11:16
#include <bits/stdc++.h>
#define int long long //就是为了防止RE,结果还是RE了...... 
using namespace std;
int L, R;//左右区间端点 
int v[50000];//线性筛里辅助数组,判断有没有被筛过 
int prime[50000]; //用于记录(0, sqrt(R)]之间的素数 
int is_prime[100050]; 
//判断[L, R]区间的一个数是不是素数,枚举i,是素数就在i - L数组下标存上i这个数,不是素数就在i - L数组下标存上0
//[L, R]区间大小为100000,所以这里数组大小开100050 
int cnt; //prime[]的计数器 
int tot; //记录[L, R]区间有多少素数 
int b[100010]; //把 [L, R]区间区间中的合数筛掉,只留下素数,下标从0到tot 

void primes(int n) //线性筛模板 
{
    memset(v, 0, sizeof(v));

    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0)
            v[i] = i, prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++)
        {
            if (prime[j] > v[i] || prime[j] > n / i)
                break;
            v[i * prime[j]] = prime[j];
        }
    }
}
signed main()
{
    while (scanf("%d%d", &L, &R) != EOF) //循环读入 
    {
    	memset(is_prime, true, sizeof is_prime);
        cnt = 0;
        tot = 1;
        primes(sqrt(R));
    	for (int i = L; i <= R; i++)
    		is_prime[i - L] = i; 
        for (int i = L; i <= R; i++)
        {
            for (int p = 1; p <= cnt; p++)
            {
			 	if (i == prime[p])
			 		continue;
                if (i / prime[p] >= (L / prime[p]) && i / prime[p] <= (R / prime[p]) && i % prime[p] == 0)
                {
                	is_prime[i - L] = 0; 
                	tot++;
                }                
            }        
        }
        
        // 筛掉合数,留下素数 
		memset(b, 0, sizeof b);
		int res = 0; 
		for (int i = 0; i <= R - L; i++)
			if(is_prime[i] != 0)
				b[res++] = is_prime[i]; 
		
		
        if (res == 1 || res == 0)//题目要求 ,素数不到两个就输出
        {
            cout << "There are no adjacent primes." << endl;
            continue;
        }
        
        //这边写的不太简介,但大概就是满足题目要求,找出相邻相差最大和最小的数,应该没什么问题 
        int tag = 0;
        int tag2 = 0;
        int tag3 = 0;
        int tag4 = 0;
        int res_min = INT_MAX;  
        int res_max = 0;
        for (int i = 1; i < res; i++)
        {
        	if(b[i] - b[i - 1] > res_max)
        	{
        		res_max = b[i] - b[i - 1];
        		tag = b[i];
        		tag2 = b[i - 1];
			}
			if(b[i] - b[i - 1] < res_min)
        	{
        		res_min = b[i] - b[i - 1];
        		tag3 = b[i];
        		tag4 = b[i - 1];
			}
		}
	
		//输出答案 
		cout << tag4 << "," << tag3 << " are cloest. " << tag2 << "," << tag << " are most distant" << endl;
    }
    return 0;
}
/*
2 17
14 17
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
*/
2020/5/11 11:16
加载中...