0

在解决一个问题以在给定范围内查找素数时，我收到一个 Sigsegv 错误，我无法找到我的错误在哪里以及如何纠正它

#include<iostream>
#include<cmath>
using namespace std;
int primes[10000000];// stores prime upto a max value
int prime[10000000];//stores prime in a given range
int main()
{
  long long int t,m,n,s,k,q;
  for(long long int i=1;i<=1000000;i++){
      primes[i]=1;
      primes[1]=0;
  }

    //stores prime using sieve    
    for(long long int i=2;i<=sqrt(1000000);i++) 
    {
        if(primes[i]==1)
        {
            for(long long int j=2;i*j<=1000000;j++)
            {
                primes[i*j]=0;
            }
        }   
    }
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        //marking all indices as 1 
        for(long long int i=m;i<=n;i++)      
        {
          prime[i]=1;
        }
        //calculating which offset to mark
        for(long long int i=2;i<=n-m+1;i++)       
        {
            if(primes[i]==1)
            {
                long long int x=(m/i)*i;
                while(x<m)
                x=x+i;   
                for(long long int j=x;j<=n;j=j+i)
                {
                    if(primes[j]==0)
                    prime[j]=0;
               }  
             }
           }         
        for(long long int i=m;i<=n;i++)
        {
            if(prime[i]==1&&i!=1)
            cout<<i<<"\n";
        }
    }
    return 0;
}
4

2 回答 2

2

您使用的编译器可能不允许静态分配大块数据，例如

int primes[10000000];

这超过 2^25 个字节。这么大的块可能会超出编译器的能力或其在 SPOJ 上的运行时。可能会有这么大new的malloc()一块，但这种解决方法可能会让你走入死胡同。

另一个问题是您在没有验证它们是否在安全范围内的情况下读取m和读取输入。nSPOJ 上的至少一个测试用例将比您的代码限制高出两个数量级，因为您的分配是 10^7，但 SPOJ 限制是 10^9。这意味着崩溃是不可避免的。

您不需要完整的 32 位整数来保存布尔值；您可以使用bool，从而将内存需求减少到四分之一。或者您可以将每个字节大小的数组单元视为具有 8 位的打包位图，与现在相比将内存使用减少到 1/32。std::vector<bool>而且由于您使用的是 C++，因此所有内容都已经以（在引擎盖下进行了一些打包）的形式为您整齐地打包。

注意：数组必须是 100 倍大才能筛选所有数字，直到 PRIME1 限制为 1,000,000,000。尽管可以筛选出该范围内的所有数字（时间限制非常大——大约是此任务所需的 10000 倍），但对于完全不熟悉编程的人来说，这可能并不容易。

但是，该任务并不要求筛选十亿个数字。它只要求筛选一小部分范围，每个范围不超过 100001 个数字。即使是简单的、未经优化的代码也可以在一毫秒内完成，即使std::vector<bool>它比任何合理的数据结构都慢一个数量级。

要注意的关键字是“埃拉托色尼的窗口筛”。代码审查中涉及 PRIME1 的主题有数百个。看一看。

于 2016-04-21T14:32:49.017 回答
0

考虑一个案例：

1
100000000 100000009

当我在 ideone 链接上运行您的代码时：这里。

它给出了运行时错误。

原因：您已初始化大小为10 7的素数数组，但范围m, n可达10 9。

因此，一旦prime[i]=1遇到，您的系统就会崩溃。

for(long long int i=m;i<=n;i++)      
{
      prime[i]=1;
}

建议：学习埃拉托色尼筛法。并且由于范围m, n可以是
1 <= m <= n <= 1000000000, n-m<=100000

如果我们取10 9的 sqrt-root ，那么它将接近31622。num所以，这就是为什么我们选择了一个大小为32000 的数组（在我的代码中）。之后，我们计算了2 - 32000范围内的素数数量。

现在，考虑三种情况：

  1. 当m and n两者都小于 32000 时。然后只需使用计算出的prime数组并打印所需的素数。

  2. 当两者m and n都在 32000 范围之外时，检查一个数字i （在 m 和 n 的范围内）是否不能被任意素数整除（存在于prime代码中的数组中）。如果不能i被任何数字整除，则打印它。

  3. 如果 的范围m and n部分小于 32000 部分在 32000 之外。然后将范围分成两部分，一个完全小于等于 32000，另一个完全大于 32000。然后重复步骤 1第一个范围和第二个范围的步骤 2。

下面是我的代码，请觉得有用，但不要复制粘贴到 SPOJ 上。

#include<stdio.h>
#include<math.h>

int num[32000] = {0},prime[3500],prime_index = -1;

int main() {
    prime[++prime_index] = 2;
    int i,j,k;

    for(i=3;    i<179;     i += 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;

            for(j = i*i, k = 2*i;    j<=32000;   j += k) {
                num[j] = 1;
            }
        }
    }

    for(;   i<=32000;   i+= 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;
        }
    }

    int t,m,n;
    scanf("%i",&t);
    while(t--) {
        scanf("%i%i",&m,&n);

        if(m == 1)
            m++;

        if(m == 2 && m <= n) {
            printf("2\n");
        }

        int sqt = sqrt(n) + 1, arr[100005] = {0};

        for(i=0;    i<=prime_index; i++) {
            if(prime[i] > sqt) {
                sqt = i;
                break;
            }
        }

        for(;   m<=n && m <= prime[prime_index];   m++) {
            if(m&1 && num[m] == 0) {
                printf("%i\n",m);
            }
        }

        for(i=0;    i<=sqt;     i++) {
            j = prime[i] * (m / prime[i]);

            if(j < m) {
                j += prime[i];
            }

            for(k=j;    k<=n;   k += prime[i]) {
                arr[k-m] = 1;
            }
        }

        for(i=0;    i<=n-m; i++) {
            if(!arr[i]) {
                printf("%i\n",m+i);
            }
        }

        printf("\n");
    }
    return 0;
}

有任何疑问欢迎评论。

于 2016-04-28T11:06:11.937 回答