Sigsegv Ошибка при поиске простого числа в диапазоне

Question

Sigsegv Ошибка при поиске простого числа в диапазоне

При решении вопроса, чтобы найти простое число в заданном диапазоне, я получаю ошибку 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;
}

0

c++primes sieve sieve-of-eratosthenes

Решение

Другие решения

Компилятор, который вы используете, может не разрешать статическое распределение больших порций данных, таких как

int primes[10000000];

Это более 2 ^ 25 байт. Такой большой кусок может превышать возможности компилятора или его время выполнения на SPOJ. Это может быть возможно new или же malloc() такой большой кусок, но этот обходной путь, вероятно, приведет вас в тупик.

Другая проблема в том, что вы читаете m а также n от ввода без проверки того, что они находятся в безопасных пределах. По крайней мере один из тестовых случаев на SPOJ будет на два порядка выше пределов вашего кода потому что ваше распределение составляет 10 ^ 7, но предел SPOJ составляет 10 ^ 9. Это означает, что крах неизбежен.

Вам не нужно полное 32-разрядное целое число для хранения логического значения; вы могли бы использовать bool и, таким образом, сократить требования к памяти до одной четвертой. Или вы можете рассматривать каждую ячейку массива байтового размера как упакованное растровое изображение с 8 битами, сокращая использование памяти до 1/32 по сравнению с сегодняшним днем. И поскольку вы используете C ++, все уже аккуратно упаковано для вас в виде std::vector<bool> (что делает упаковку под капотом).

Примечание: массивы должны быть в сто раз больше для просеивания всех чисел до предела PRIME1 в 1 000 000 000. Хотя можно просеять все числа в этом диапазоне (ограничение по времени более чем щедрое — примерно в 10000 раз больше, чем нужно для выполнения этой задачи), для человека, который является совершенно новым для программирования, это, вероятно, не легко.

Однако задача не требует просеивания миллиарда чисел. Требуется только просеивание небольшого количества диапазонов, каждый из которых не шире 100001 номеров. Даже простой неоптимизированный код может сделать это за миллисекунду, даже если std::vector<bool> что на порядок медленнее, чем любая разумная структура данных.

Ключевое слово, на которое нужно обращать внимание, — «Сито Эратосфена». Здесь и снова есть сотни тем на Code Review, которые касаются PRIME1. Есть заглянуть.

2

Источник

Accepted Answer

Рассматривать случай:

1
100000000 100000009

Когда я запустил ваш код по ссылке ideone: Вот.

Это дало Ошибка во время выполнения.

Причина: Вы инициализировали простой массив размера 10⁷ но диапазон m, n может доходить до 10⁹.

Поэтому однажды prime[i]=1 встречается, ваша система падает.

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

Предложение: Изучите сито Эратосфена. И так как диапазон m, n может быть
1 <= m <= n <= 1000000000, n-m<=100000

Если мы возьмем sqrt-корень 10⁹ тогда он приблизится к 31622. Итак, вот почему мы подобрали массив num размера 32000 (в моем коде). После этого мы вычислили число простых чисел, лежащих в диапазоне 2 — 32000.

Теперь рассмотрим три случая:

когда m and n оба меньше, чем 32000. Тогда просто используйте рассчитанный prime массив и распечатать необходимые простые числа.
Когда оба m and n находятся за пределами диапазона 32000, затем проверьте, является ли число i (в диапазоне м и н) является не делится на любое простое число (присутствует в prime массив в коде). Если i является не делится на любое число, а затем распечатать его.
Если диапазон 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;
}

Любые сомнения комментарии приветствуются.

0