Генерация простых чисел в диапазоне в C++


Мне дали задачу найти все простые числа в диапазоне. Только после того, как я написал программу, я нашел множество других кодов, чтобы решить проблему. Мне интересно узнать мой алгоритм эффективной? Это как сито фильтрации? (прежде чем писать этот код у меня не было четкого представления о методе фильтрации сито) или алгоритм я использовал это плохо?

#include<iostream.h>
#include<math.h>

prime_gen

void prime_gen(int a,int b)
{
    int array[4]={2,3,5,7},holder[1000000]={0},count=0,flag=0,length=0,number_count=0;

    for(int i=0;i<b;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(i==array[j])
            {
                break;
            }
            else
            {
                if(i%array[j]==0)
                {
                    count++;
                }
            }
        }
        if(count==0)
        {
            if(i>1)
            {
                holder[length++]=i;
            }
            else
            {
                length=0;
            }
        }
        count=0;
    }   

    if(length==0)
    {   
        cout<<"No prime numbers exist within the range";
        cout<<"\n";
    }                               
    else 
    {                                                               
        cout<<"Prime numbers are:";

        for(int i=0;i<length;i++)
        {                                                                                   
            int t=holder[i];

            for(int check=0;check<sqrt(length);check++)
            {

                if(t!=holder[check])
                {
                    if(t%holder[check]==0)
                    {
                        t=0;
                    }
                }
            }

            if(t!=0&&t>=a)
            {
                number_count++;
                cout<<t<<"\t";
            }
        }

        cout<<"Total count:"<<number_count<<endl;
    }
}

главная

int main()
{
    int a,b;

    cout<<"Put the first integer:";
    cin>>a;

    cout<<"Put the second integer:";
    cin>>b;

    prime_gen(a,b);
}


2586
6
задан 12 ноября 2011 в 11:11 Источник Поделиться
Комментарии
4 ответа

Стилистические заметки:


  • Использовать несколько пробелов вокруг знаков препинания (для(int я=0;я хочет ветер), не посыпать коде пустые строки в случайных местах, и использовать последовательного вдавливания.

  • Объявлять переменные в отдельных строках; используйте пустое пространство справа, чтобы написать комментарий, объясняющий, что переменная для.

  • Используйте осмысленные имена переменных. Давай, массив? Читатель может увидеть, что это массив, но как его содержать?

Кроме того, сделать свой ум: вы пишете на C++, а не C. Некоторые части (такие как использование массивы C) не идиоматических на C++, хотя; вы должны выбрать один, либо С (и использовать студию, но не понял зачем) или C++ (и использовать новые и стл). Так как я с программистом, но не знаете с++, я буду комментировать с-иш части и не сказать ничего об идиоматических на C++.

В массив переменной не полезно здесь. Малых простых чисел появится в держатель массива в любом случае, так что ставьте их непосредственно. Даже если вы занимались простые сомножители специально, ваш счетчик переменной бесполезно: вам не нужно подсчитывать, сколько малых простых чисел разделить меня, вы только должны знать, является ли небольшие премьер-делит я.

Также, вы могли бы также использовать целые числа без знака для переменных, так как они не содержат отрицательных чисел.

unsigned holders[1000000]; /* list of prime numbers */
unsigned length = 0;
holders[length++] = 2;
holders[length++] = 3;
holders[length++] = 5;
holders[length++] = 7;

Вам не нужно, чтобы полностью инициализировать держатели, так как вы будете только смотреть на первую длину элементов. Конечно, можно писать без знака держатели[1000000] = {3, 5, 7}; и компилятор будет заполнить остальные с нулями, с типичной реализации, это приведет к полному спектру (нули включены) записывается в исполняемый файл, который является огромной тратой.

Вы должны быть выделения держатели динамически в любом случае, и проверяя его размер. Если кто-то проходит такое большое значение для б , что держатели массив переполнится, ваш код будет перезаписать произвольную память. Как вычислить размер держателей массива, так что это достаточно большой, учитывая Б, или следить за своим размером и продлить его, если длина будет слишком большой.

Даже цифры не Прайм. Таким образом, вместо перебирая все целые числа, перебрать все нечетные целые числа.

Нет никаких причин, чтобы заполнить держатели номера-простые числа. Первый цикл может быть ликвидирована.

for (x = 11; x < b; x += 2) {
bool is_prime = true;
// start j at 1.
// As holders[0] is 2 and no value of x is divisible by 2.
for (j = 1; j < length && holders[j] <= sqrt(x); j++) {
if (x % holders[j] == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
holders[length++] = x;
}
}

Теперь, чтобы найти количество простых чисел между А и Б, траверс держатели набор из первое значение больше или равно а. Когда вы написать полную программу, позаботиться о граничных условий; в частности, убедитесь в том, чтобы считать 2, Если а ≤ 2.

for (j = 0; j < length; j++) {
if (holders[j] >= a) break;
}
return length - j;

6
ответ дан 13 ноября 2011 в 10:11 Источник Поделиться

Ваш код не является правильным, следовательно, его эффективность не имеет никакого отношения. Вы только проверить на делимость на 2, 3, 5 и 7, так что вы бы классифицировать напр., 121 = 11*11 премьер.

5
ответ дан 12 ноября 2011 в 11:11 Источник Поделиться

Моя версия сито в http://ideone.com/1AP8uи функция, которая выполняет просеивание показана ниже. Объяснения на мой блог, посмотрите на "простых чисел" в "темы" тег в разделе "упражнения" меню пункт.

struct node* sieve(int n) {
int m = (n-1) / 2;
char b[m/8+1];
int i=0;
int p=3;
struct node* ps = NULL;
int j;

ps = insert(2, ps);

memset(b,255,sizeof(b));

while (p*p<n) {
if ISBITSET(b,i) {
ps = insert(p, ps);
j = 2*i*i + 6*i + 3;
while (j < m) {
CLEARBIT(b,j);
j = j + i + i + 3; } }
i+=1; p+=2; }

while (i<m) {
if ISBITSET(b,i) {
ps = insert(p, ps); }
i+=1; p+=2; }

return reverse(ps); }

4
ответ дан 13 ноября 2011 в 03:11 Источник Поделиться

"держателем[1000000];" массив живет на стеке ("автоматическая переменная"). Я бы по крайней мере сделать его статическим, поскольку он может быть повторно использованы, и много работы ушло на это (что предполагает отсев unsieved записи, но для реальной программы (и функция, которая вызывается более чем один раз) это была бы победа.

1
ответ дан 13 ноября 2011 в 12:11 Источник Поделиться