АлгоритмыПростые числа (Часть 2). Нахождение палиндромов


С момента последней статьи пришлось внести несколько оптимизаций, которые уменьшили время нахождения 100000-ного простого числа с 4,552 до 1,224 секунды. И эта разница с ростом чисел будет увеличиваться.
В обе функции я внес следующие оптимизации:
— поиск только по нечетным числам (так как кроме числа 2 больше нет четных простых чисел);
— находим корень числа для конечного диапазона не каждый раз в цикле, а только когда это необходимо;
— для проверки числа на простоту делим только на нечетные числа.
Первая функция. Если число, которое мы передали в функцию, простое, функция возвратит 1, если нет, то 0.
int PrimeNumber(int number)
{
  int MaxNumber;

  // отсеиваем все четные числа
  if (number%2 == 0 && number != 2)
  {
    return 0;
  }
  if (number == 2)
  {
    return 1;
  }

  // находим последний элемент цикла, до которого будем делить число для проверки на простоту
  MaxNumber = sqrt(number)

  for (int i=3; i<MaxNumber; i+=2)
  {
    // проверяем наше число на остаток по всем нечетным числам начиная от тройки
    if (number%i == 0)
    {
      return 0;
    }
  }

  return 1;
}


Вторая функция. Эта функция находит первое простое число, которое находится за числом, которое мы передаем в функцию.
int NextPrimeNumber(int previous)
{
  int temp;
  int MaxNumber;
  int i = 3;

  if (previous == 2)
  {
    return 3;
  }
  else
  {
    temp = previous + 2; // идем только по нечетным числам
  }

  MaxNumber = sqrt(temp);

  while (1)
  {
    if (temp%i == 0 && i!=temp)
    {
      temp += 2;
      MaxNumber = sqrt(temp);
      i=3;
      continue;
    }

    if (i>MaxNumber)
    {
      break;
    }

    i += 2;
  }

  return temp;
}


Палиндромы
В проекте «Эйлер» попалась задачка, в которой встретил такое понятие как палиндром. Это числа, которые читаются в обоих направлениях одинаково (1001, 55, 474, 2, 12521...). Я написал функцию, которая проверяет, является ли число палиндромом.
Если число, которое мы передаем в в функцию GetPalindrome(), является палиндромом, функция возвращает единицу, если нет — ноль.
int GetPalindrome(int pal)
{
  int next = 0;
  int pal2 = pal;

  while (pal2 != 0)
  {
    next = (next * 10) + (pal2 % 10);
    pal2 /= 10;
  }

  if (pal == next)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}
  • +3
  • eReS
  • 06 января 2011, 00:12

Комментарии (9)

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

По идее, компилятор должен такие вещи сам находить.
Оно реально ускоряет работу программы?
Да, можете «MaxNumber = sqrt(temp);» перенести в главный цикл, заодно и проверите :)
Лениво мне было самому делать =)
Итого: gcc версия 4.4.4 (Gentoo 4.4.4-r2 p1.2, pie-0.4.5)
Функция 1:
g++: 1.010000
g++ -O3 -mmmx -msse -msse2 -mfpmath=sse -funroll-loops: 0.720000

Функция 1 после переноса:
g++:1.530000
g++ -O0: 1.530000
g++ -Os: 1.330000
g++ -O1 и -O2 и -O3: 0.820000
g++ -O3 -mmmx -msse -msse2 -mfpmath=sse -funroll-loops:0.780000

Все цифры очень приблизительны — значения скакали с погрешностью до 0.2с (и почему-то занимали некоторые «устойчивые положения»), видимо криво время мерюю:

clock_t begin = clock();
// do thomething
float time = (clock() - begin)/(float)CLOCKS_PER_SEC;

Итого: компилятор умеет отлавливать такие ситуации.
:) если у вас Gentoo, есть намного проще способы измерять время работы программы, командой time:
$ time ./имя_скомпилированной_программы

Исходник для проверки Задачи №7:

#include <iostream>
#include <cmath>
using namespace std;

int NextPrimeNumber(int previous)
{
  int temp;
  int MaxNumber;
  int i = 3;

  if (previous == 2)
  {
    temp = previous + 1;
  }
  else
  {
    temp = previous + 2;
  }

  MaxNumber = sqrt(temp);

  while (1)
  {
    if (temp%i == 0 && i!=temp)
    {
      temp += 2;
      MaxNumber = sqrt(temp);
      i=3;
      continue;
    }

    if (i==temp || i>MaxNumber)
    {
      break;
    }

    i += 2;
  }

  return temp;
}

int main()
{
  int nux = 2;		// первое простое число, от которого начинаем поиск
  int number = 100000;	// простое число, которое нужно найти
	
  for (int i=1; i<number; i++)
  {
    nux = NextPrimeNumber(nux);
  }

  cout << number << " простое число: " << nux << endl;

  return 0;
}

// 100000-ше простое число: 1299709
// real	0m1.217s
Функцию «int NextPrimeNumber(int)» лучше взять из поста, ибо здесь по ошибке устаревшую версию кинул.
Не понял, почему именно Gentoo?
Ну я имел ввиду «не виндовс», time — линуксовая утилита.
С тем же успехов в visual studio есть profiler. Кстати им всё-таки лучше замерять :)
Да можно и по количеству тактов замерять — будет «всё-таки лучше»…
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.