Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:hhh重新写了一遍过了...确实理清了不少思路

Posted by sailist at 2019-03-21 10:53:53 on Problem 2689
In Reply To:很多数据都测试过了成功了,句子也确定没有错但还是WA...不知道什么情况 Posted by:sailist at 2019-03-19 21:17:50
#include <stdio.h>
#include <cstring>
#include <iostream>

using namespace std;

#define small 50000
#define prime 0
#define notPrime 1

int offset_numbers[2000001];
bool sqrt_b[small];

#define isPrime(x) x == 0

void iniSmallPrime()
{
    sqrt_b[0] = notPrime;
    sqrt_b[1] = notPrime;
    for (int i = 2; i <= small; ++i) {
        if(sqrt_b[i] == 0)
        {
            for (int j = 2*i; j <= small ; j+=i) {
                sqrt_b[j] = notPrime;
            }
        }
    }
}

void solveBigPrime(int l,int r)
{

    for (unsigned int i = 2; i*i <= r ; ++i) {
        if(isPrime(sqrt_b[i]))
        {
            int start = l%i == 0? l:l-l%i+i;
            if(start == i)
            {
                start += i;
            }
            for (int j = start; j <= r & j>=l ; j+=i) {
                offset_numbers[j-l] = notPrime;
            }
        }
    }
    if(l == 1)
    {
        offset_numbers[0] = notPrime;
    }
}


int main() {
    memset(sqrt_b,prime, sizeof(sqrt_b));
    iniSmallPrime();
    int l,r;
    while(~scanf("%d %d",&l,&r))
    {
        memset(offset_numbers,prime, sizeof(offset_numbers));
        solveBigPrime(l,r);
        int minL=0,minR=0,maxL=0,maxR=0;
        int minD = 1000000,maxD = 0;
        int start = 0;
        bool have = false;
        while(start <= r-l-1)
        {
            if(isPrime(offset_numbers[start]) && start<= r-l-1)
            {
                int i = start+1;
                while (!isPrime(offset_numbers[i]) && i<=r-l)
                {
                    i++;
                }
                if(i>r-l)
                {
                    break;
                }
                if(minD > i-start)
                {
                    minD = i-start;
                    minL = start+l;
                    minR = i+l;
                }
                if(maxD < i-start)
                {
                    maxD = i-start;
                    maxL = start+l;
                    maxR = i+l;
                }
                have = true;
                start = i;

            } else
            {
                start++;
            }
        }
        if(have)
        {
            printf("%d,%d are closest, %d,%d are most distant.\n",minL,minR,maxL,maxR);
        } else
        {
            printf("There are no adjacent primes.\n");
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator