Оптимизация кода простых чисел?

Question

Я написал этот код, чтобы показать простые числа от 1 до 100. Единственное условие - не использовать функции, весь код должен быть встроенным. Я бы спросил, могу ли я улучшить (оптимизировать) это намного больше?

#include<iostream>

using namespace std;

int main() {

    int i=2,j=2;

    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    while(i!=100) {
        for(int j=2;j<i;j++) {
            if(i%j==0)
            break;

            if(j==i-1)
            cout<<i<<"\t";
        }

        i++;
    }

    cout<<endl;
    system("pause");
    return 0;
}

Answer 1

Избегайте использования функции квадратного корня и увеличивайте делитель на 2. Также некоторые хитрые вещи в цикле i увеличивают возможное простое число на 2. Внутреннему циклу даже не нужно проверять делимость на 2, поскольку четные числа не будутдаже быть проверенным.

int i,j,sq;
int min;
for(sq = 2; sq <= 10; sq++)
{
  min = (sq-1)*(sq-1);
  min = min + (min+1)%2; //skip if it's even, so we always start on odd
  for(i = min; i < sq*sq; i+=2)
  {
    for(j = 3; j <= sq; j+=2)
    {
      if (i%j == 0)
        bad;
    }
  }
}

обратите внимание, что цикл sq не добавляет времени, потому что он пропорционально сжимает внутренние циклы.

Answer 2

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

int main() {
    cout << "Prime numbers are:" << endl << "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97" << endl;
    return 0;
}

Answer 3

Вы можете оптимизировать существующий код:

• В цикле while у вас должен быть шаг 2, чтобы вы не проверяли четные числа.
• В вашем дляцикл, который вы должны прекратить, когда достигнете квадратного корня числа, которое вы тестируете*

На Сите Эрастозов просто удаление чисел, кратных 2,3 и 5, значительно уменьшит количество проверок на простоту.

Answer 4

    for(int j=2;j<i;j++){

Этот не хороший.

Прежде всего, вам нужно только проверить на j <= sqrt(i), так как, например, 7 никогда не разделит 12 без отдыха.

Во-вторых, вы должны отслеживать все ранее найденные простые числа; держите его в векторе и делайте этот цикл только для его содержимого и для того условия, которое я написал.

Answer 5

Вы проверяете каждое число от 2 до 100. Но так как 2 является единственным четным простым числом, вы можете пропустить каждое четное число после 2. Это относится как к i, так и к j.Итак, начните i и j с 3 и увеличивайте их на 2.

#include<iostream>

using namespace std;

int main() {
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    for (int i=3; i<100;i+=2) {
        // This loop stops either when j*j>i or when i is divisible by j.
        // The first condition means prime, the second, not prime.
        int j=3;
        for(;j*j<=i && i%j!=0; j+=2); // No loop body

        if (j*j>i) cout << i << "\t";
    }
    cout<<endl;
    return 0;
}

В дополнение к упомянутому трюку, я добавил условие j*j<=i, которое логически точно такое жекак j<=sqrt(i).Нет необходимости вычислять квадратный корень, когда вы можете выполнить простое умножение.

Answer 6

Две простые оптимизации, которые вы можете сделать:

cout << 2 << '\t';
for (int i = 3; i <= 100; ++i) {
    for (int j = 3, l = (int)sqrt(i); j <= l; j += 2) {
        if (i % j == 0) {
            cout << i << '\t';
            break;
        } 
} 

Что я сделал:

Math:

• Стоп, когда j > sqrt(i), нет необходимости идти дальше. Обратите внимание, что sqrt - дорогая функция; для вашей небольшой выборки (от 1 до 100) может потребоваться (читай, наверняка ) дороже.
• Проверять только нечетные числа; делать j += 2 вместо увеличения j один за другим

Micro-оптимизации:

• Используйте ++i вместо i++; последний имеет временную переменную, в которой хранится исходное значение i; первый нет.
• Печать '\t' в виде символа, а не строки "\t".

(Эти микрооптимизации, вероятно, все равно выполняются компилятором автоматически, но знать о них не вредно.)

Answer 7

Зависит от того, какую оптимизацию вы хотите сделать. Ваш настолько хорош, насколько возможно, чтобы я мог видеть, оптимизируете ли вы сначала пространство, потом секунду (ну, близко - пока вы слушаете @Paul, это будет) Если вы поменяете приоритеты, сито эрастотенов будет быстрее (но займет 100 логических единиц вашей памяти).

Answer 8

/*** Return an array of primes from 2 to n. ***/
int[] function nPrimes(int n) {
   int primes[];  //memory allocation may be necessary depending upon language.
   int p = 0;
   bool prime;
   for (int i = 2; i <= n; i++) {
       prime = true;
       //use (j <= (int)sqrt(i)) instead of (j < i) for cost savings.
       for (int j = 2; j <= (int)sqrt(i); j++)  {
           if (i % j == 0) {
               prime = false;
               break;
           }
       }
       if (prime) {
           primes[p++] = i;
       }    
   }
   return primes;
}

Answer 9

Самый эффективный способ сделать это - Сито Эратосфена. Вот инкрементная версия, специально предназначенная для создания простых чисел до 100 , одна за другой (максимум до 120 , потому что 121 == 11 * 11 ) .

printf("2 ");
int m3=9, m5=25, m7=49, i=3;
for( ; i<100; i+=2 )
{
    if( i!=m3 && i!=m5 && i!=m7) printf("%d ", i);
    else
    {
        if( i==m3 ) m3+=6;
        if( i==m5 ) m5+=10;
        if( i==m7 ) m7+=14;
    }
}