需要使代码高效并降低时间复杂度

Question

给定范围 [ L , R ]（包括两者），我必须找出给定范围内两个素数之间的最大差值。对于给定的范围，可能有三个答案。

如果在给定范围内只有一个不同的素数，那么这种情况下的最大差值为 0。

如果给定范围内没有素数，则这种情况的输出将为 -1。

示例：

Range: [ 1, 10 ]

The maximum difference between the prime numbers in the given range is 5.

Difference = 7 - 2 = 5


Range: [ 5, 5 ]

There is only one distinct prime number so the maximum difference would be 0.


Range: [ 8 , 10 ]

There is no prime number in the given range so the output for the given range would be -1.

输入格式输入的第一行包含测试用例的数量，T

接下来的 T 行，每行由两个 space 分隔的整数组成，L 和 R

约束条件 1<= T <=10

2<=长<=右<=10^6

这是我的代码：

    #include <stdio.h>
    int isprime(int n)
    {
        int i,c=0;
        for(i=1;i<n;i++)
        {
            if(n%i==0)
             c++;
        }
        if(c==1)
         return 1;
        else
         return 0;
    }
    
    int main()
    {
        int t; //testnumber
        scanf("%d",&t);
        for(int k=0;k<t;k++)
        {
         int l,r; //l=low or floor, r = highest range or ceiling;[l,r]
         scanf("%d%d",&l,&r);
         int n = r-l; //difference in range
         int a[n]; 
         int j=0;
         for(int i=l;i<=r;i++)
         {
             if(isprime(i)==1)
             {
                a[j] = i;
                j++;
             }
         }
         int d = a[j-1]-a[0];
         if(j==0)
          printf("%d\n",-1);
         else
          printf("%d\n",d);
        } 
        return 0;
    }

Answer 1

此任务不需要任何特殊算法（除了在 O(sqrt(N)) 中检查数字是否为素数）即可高效解决。想一想质数，它们在某个范围内（例如从 1 到 100 的范围内）出现的频率是多少？出现的某种“模式”是什么。现在，如果我正确地理解了这个任务，你需要找到 last_prime_on_range - first_prime_on_range 范围内素数的最大差异，根据这次和之前的观察，你可以轻松设计出一种有效的算法。

剧透：

你不需要检查整个范围，检查从 L 到 L+100 就足够了从 R 到 R-100，显然如果 L+100>R 你可以从 L 到 R。如果您想确定可以从 L 到 L+1000 以及从 R 到 R-1000，因为它不会对时间复杂度产生太大影响。另外，在找到质数时添加 break; 也可以解决问题。请注意，素数之间的差距不能保证低于 100/1000，但对于给定的范围，检查高达 1000 就足够了。

现在如果你需要检查范围内的所有质数，你应该了解 Sieve Of Eratosthenes。

Answer 2

在 forum/stack 上发帖或要求审核时，请尝试适当地命名您的变量。否则，很难遵循代码或哪个变量的用途。

我写了下面的代码希望你能理解我的实现。

#include <iostream>
#include <math.h>
using namespace std;

void isPrime(int num, int* primeNumber)
{
    if (num == 2)
    {
        *primeNumber = num; //2 is a prime number
        return;
    }
    if (num%2 == 0)
    {
        return; //num is an even number, so, not prime
    }
    int limit = sqrt(num);
    if (limit*limit == num)
    {
        return; //num is a square number, so, not prime
    }
    for (int i = 3; i <= limit; i=i+2)//to find if a number is prime or not, we only have to divide it from 2 to sqrt(num).
    {          //i=i+2 skips even number, cause already checked if num is even or not.
        if (num % i == 0)
        {
            return; //`num` is divisible by i, so, not prime
        }
    }
    *primeNumber = num; //no divisible number found. so, num is prime.
}

int main() 
{
    int testNumber;
    cout<< "Enter testNumber: ";
    cin>> testNumber;

    for (int i = 0; i < testNumber; ++i)
    {
        int  newLow, low, high, lowestPrime = 0, highestPrime = -1;
        cin>> low>> high;
        newLow = low;
        if (low == high)
        {
            cout<<"0\n";
            continue;
        }

        for (int j = low; j <= high; ++j)//find the lowest prime
        {
            isPrime(j, &lowestPrime);
            if (lowestPrime != 0)//if lowest prime found, lowestprime will no longer be 0
            {
                //cout<<"lowest prime: "<<lowestPrime<<endl;
                newLow = j; //there is no prime number between low...newLow
                break;
            }
        }

        for (int j = high; j >= newLow; j--)//find highest prime
        {
            isPrime(j, &highestPrime);
            if (highestPrime != -1)//if highest prime found, highestprime will no longer be -1
            {
                //cout<<"highest prime: "<<highestPrime<<endl;
                break;
            }
        }

        cout<<highestPrime - lowestPrime<<"\n";
    }

    return 0;
}

需要使代码高效并降低时间复杂度

Need to make code efficient and reduce time complexity

c

time

time-complexity