Я пытаюсь спроектировать сито эратосфенов на C, но столкнулся с двумя странными проблемами, которые не могу понять. Вот мой основной план программы. Попросите пользователей установить диапазон для отображения простых чисел. Если минимум диапазона ниже 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 объявлены ранее как ints, и в них включен 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 отсеиваются, и я не могу понять, почему это происходит со все большим количеством младших чисел, поскольку цифры вырос.
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;
}
}
Спасибо, что прочитали все это! Прошу прощения за публикацию еще одного вопроса, связанного с ситом эратосфена, и заранее благодарю вас за помощь!