primenumber

Пример 1

Нахождение простых чисел с помощью "решета Эратосфена".

Конкретизируем задачу. Простые числа - это такие числа, которые имеют только два множителя: 1 и это число. Другими словами, простой число делится только на 1 и на само себя. Метод нахождения простых числе с помощью "решета Эратосфена" заключается в следующем. Выписываем все числа от двойки до заданного числа. Два - простое число. Зачеркиваем все остальные четные числа. Переходим к тройке и зачеркиваем после нее каждое третье число. Находим следующее незачеркнутое. Это пять и зачеркиваем далее каждое пятое и т.д.. Таким образом в конце все незачеркнутые числа будут простыми.

Разобьем задачу на два шага. На первом шаге, мы непосредственно реализуем этот алгоритм, а на втором займемся выводом результатов.

str   input
uint  high i j

print("This program uses \"The Sieve of Eratosthenes\" for finding prime numbers.\n\n")
high = uint( congetstr("Enter the high limit number ( < 100000 ): ", input ))
if high > 100000 : high = 100000

arr  sieve[ high + 1 ] of byte

fornum i = 2, high/2 + 1
{
   if !sieve[ i ]
   {
      j = i + i
      while j <= high
      {
         sieve[ j ] = 1
         j += i
      }
   }
}

В начале мы просим пользователя ввести число до которого мы будем находить простые числа. Ограничим это число 100000 чтобы не занимать много ресурсов.

arr  sieve[ high + 1 ] of byte

Это описание массива байтов sieve. Нумерация элементов массива начинается с нуля поэтому увеличиваем на 1 его размер. Все массивы и переменные при создании инициализируются нулями. Таким образом, решим, что если элемент массива равен 0, то соответствующее число не зачеркнуто. Если зачеркиваем число, то ставим там 1.

В цикле fornum мы проходим только по половине чисел. Этого достаточно, а почему - подумайте сами. Далее мы реализуем сам алгоритм. Как видите, это занимает несколько строк. Мы предлагаем Вам разобрать его работу в качестве упражнения.

j += i

Это увеличение переменной j на i. Есть аналогичные операции для умножение, деления и вычитания.

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

j = 0
input.setlen( 0 )

fornum i = 2, high + 1
{
   if !sieve[ i ]
   {
      input.out4( "%8u", i )
      if ++j == 10 
      {
         j = 0
         input += "\l"
      }
   }
}

input.write( "prime.txt" )
shell( "prime.txt" )

Описание метода out4 можно найти в документации. В данном случае мы каждое число дополняем пробелами до ширины в 8 символов. Кроме этого переходим на новую строку после вывода каждых 10 чисел. За это отвечает переменная j.

В текстовых файлах для обозначения новой строки обычно используется комбинация возврата каретки '\r' и перевода строки '\n'. В Gentee для этого служит одна команда '\l'.

Метод write записывает строку в файл, а функция shell открывает указанный файл в соответствующем для данного файла приложении.

Исходники

• samples/primenumber/eratosthenes.1.g