Сокращение использования памяти при проектировании сита из эратосфена в С
Я пытаюсь создать сито из эратосфена в С, но столкнулся с двумя странными проблемами, которые я не могу понять. Вот мой основной набросок программы. Попросите пользователей установить диапазон для отображения простых чисел. Если минимум диапазона ниже 9, установите минимум как 9. Заполните массив всеми нечетными числами в диапазоне.
1) Я пытаюсь уменьшить использование памяти, объявив массивы переменного размера следующим образом:
if (max<=UINT_MAX)
unsigned int range[(max-min)/2];
else if (max<=ULONG_MAX)
unsigned long int range[(max-min)/2];
else if (max<=ULLONG_MAX)
unsigned long long int range[(max-min)/2];
Почему это не компилируется? Переменные min и max объявляются как целые числа ранее, а limit.h включен. Я закомментировал структуру выбора и только что объявил unsigned long long int range[(max-min)/2]; на данный момент, который компилирует и работает на данный момент.
2) Мой код выполняется, но иногда он помечает небольшие простые числа как не простые.
#include<stdio.h>
#include<limits.h>
void prime(int min, int max)
{
int i, f=0;
//declare variable size array
/*if (max<=(int)UINT_MAX)
unsigned int range[(max-min)/2];
else if (max<=(int)ULONG_MAX)
unsigned long int range[(max-min)/2];
else if (max<=(int)ULLONG_MAX)*/
unsigned long long int range[(max-min)/2];
//fill array with all odd numbers
if (min%2==0)
{
for (i=min+1;i<=max;i+=2)
{
range[f]=i;
f+=1;
}
}
else
{
for (i=min;i<=max;i+=2)
{
range[f]=i;
f+=1;
}
}
//assign 0 to cell if divisible by any number other than itself
for (i=3;i<=sqrt(max);++i)
{
for (f=0;f<=((max-min)/2);f++)
{
if (range[f]%i==0 && f!=i)
range[f]=0;
}
}
//troubleshoot only: print full range
for (f=0;f<=((max-min)/2);f++)
{
printf("ALL: %d / %d\n", f, range[f]);
}
//display all primes
if (min==9) /*print primes lower than 9 for ranges where min<9*/
printf("2\n3\n5\n7\n");
for (f=0;f<=((max-min)/2);f++) /*print non 0 numbers in array*/
{
if (range[f]!=0)
printf("%d\n", range[f]);
}
}
int main(void)
{
int digits1, digits2;
printf("\n\n\nCalculate Prime Numbers\n");
printf("This program will display all prime numbers in a given range. \nPlease set the range.\n");
printf("Minimum: ");
scanf("%d", &digits1);
if (digits1<9)
digits1=9;
printf("Maximum: ");
scanf("%d", &digits2);
printf("Calculating...");
printf("All prime numbers between %d and %d are:\n", digits1, digits2);
prime(digits1, digits2);
getchar();
getchar();
}
Например, если цифры =1 и цифры 2=200, моя программа выводит все простые числа от 1 до 200, кроме 11 и 13. 11 и 13 просеиваются, и я не могу понять, почему это происходит с более и более низкими числами, так как цифры 2 выросла.
3) Наконец, является ли мое сито надлежащим ситом из эратосфена? Это работает, но я чувствую, что есть более эффективный способ отсеивания не простых чисел, но я не могу понять, как это реализовать. Одна из моих целей в этой программе - быть максимально эффективной. Опять же, сейчас у меня есть:
//assign 0 to cell if divisible by any number other than itself
for (i=3;i<=sqrt(max);++i)
{
for (f=0;f<=((max-min)/2);f++)
{
if (range[f]%i==0 && f!=i)
range[f]=0;
}
}
Спасибо за чтение всего этого! Я прошу прощения за то, что выложил еще один вопрос, связанный с эратосфеном, и заранее благодарю за помощь!
2 ответа
Нет, это не правильное сито Эратосфена. Никакое тестирование остатков не вовлечено в алгоритм сита Эратосфена, Википедия действительно ясно об этом, я думаю.:) Весь смысл в том, чтобы избежать пробных делений, получить простые числа бесплатно, без тестирования.
Как? Производя их кратные, от каждого простого числа, которое мы идентифицируем, в порядке возрастания один за другим.
Кратные простого числа p: 2p, 2p + p, 2p + p + p,...
Нечетные кратные простого числа p: 3p, 3p + 2p, 3p + 2p + 2p,...
Перечисляя их, мы помечаем их в массиве sieve. Некоторые будут отмечены дважды или более, например, 15 будут отмечены для 3 и для 5 (потому что 3 * 5 == 5 * 3). Таким образом, мы можем начать перечисление и маркировку с p2:
for( i=3; i*i < n; i += 2 )
if( !sieve[i] ) // if `i` is not marked as composite
for( j = i*i; j < n; j += 2*i )
{
sieve[j] = 1; // 1 for composite, initially all are 0s
}
Ключ к решетке таков: мы не храним числа в массиве. Это не массив INTs; это массив 1-битных флагов со значением 0 или 1. Индекс записи в массиве сит обозначает номер, для которого сито сохраняет свой статус: помеченный, т.е. составной, или еще не помеченный, т.е. потенциально простой.
Итак, в конце концов, все неотмеченные записи обозначают простые числа. Вам, конечно, нужно будет разработать схему адресации, например, запись в индексе. i может соответствовать числу a + 2*i где a нечетное начало диапазона. Поскольку ваш диапазон начинается с некоторого смещения, эта схема известна как сито Эратосфена. Скелетная реализация C здесь.
Чтобы минимизировать использование памяти, мы должны рассматривать наш массив как битовый массив. В C++, например, это легко: мы объявляем это как vector<bool> и он автоматически упакован для нас. В Си нам придется немного упаковать и распаковать себя.
Совет: не переходите на временные переменные. Назовите каждую значимую сущность в вашей программе. Там не должно быть никаких (max-min)/2 в вашем коде; но вместо этого определить width = max - min и используйте это имя. Оставьте оптимизации в малом компилятору.:)
На ваш первый вопрос: это предметная область. Ваш код эквивалентен
if (max<=UINT_MAX)
{ unsigned int range[(max-min)/2]; } // note the curly braces!
else if (max<=ULONG_MAX)
{ unsigned long int range[(max-min)/2]; }
else if (max<=ULLONG_MAX)
{ unsigned long long int range[(max-min)/2]; }
так что есть три range объявления массива здесь, каждый в своей области видимости, внутри соответствующего блока. Каждый создается на входе в свой блок ({) и уничтожается при выходе из него (}). Другими словами, он не существует для остальной части вашего prime функционировать больше. Практически это означает, что если вы объявите свою переменную внутри if блок, вы можете использовать его только внутри этого блока (между соответствующими скобками { а также }).
Q1: вы не можете объявить символ (здесь: range) дважды в одной области. Это не совсем ваша проблема, но вы пытаетесь это сделать: вы объявляете range в пределах if размах и не видно снаружи.