Евразийский
научный
журнал

Простые числа- алгоритм поиска.

Поделитесь статьей с друзьями:
Автор(ы): Саковцев Владимир Павлович
Рубрика: Физико-математические науки
Журнал: «Евразийский Научный Журнал №7 2016»  (июль)
Количество просмотров статьи: 1091
Показать PDF версию Простые числа- алгоритм поиска.

Саковцев Владимир Павлович
Соискатель
E-mail: pereplet_documentov@mail.ru
Россия, г. Челябинск

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

Для явного понимания сути вопроса необходимо рассмотреть следующую таблицу:

6

12

18

24

30

36

42

48

54

60

66

72

78

84

90

96

102

5

11

17

23

29

35

41

47

53

59

65

71

77

83

89

95

101


4

10

16

22

28

34

40

46

52

58

64

70

76

82

88

94

100

3

9

15

21

27

33

39

45

51

57

63

69

75

81

87

93

99

2

8

14

20

26

32

38

44

50

56

62

68

74

80

86

92

98

1

7

13

19

25

31

37

43

49

55

61

67

73

79

85

91

97


Здесь числа расположены по возрастающей, столбиками по шесть. Подчеркнём первый и пятый ряд.

Как видно из таблицы, простые числа расположены в этих двух рядах.

Теперь введём понятие - ряд простых чисел. Ряд первый - числа определяются по формуле:

6n+1, где n- натуральное число.

Ряд пятый: 6n-1.

Как видим, в этих двух рядах расположены не только простые числа, но и натуральные. В первом ряду числа: 25,49,55,85,91 и т.д. В пятом ряду числа: 35,65,77,95 и т.д.

Данные числа определяются следующим образом:

 5x5=25  7x11=77  5x11=55  5x17=85
 5x7=35  7x13=91  и т.д.  

Все натуральные числа, расположенные в рядах простых чисел, находятся путём произведения простых чисел.

 Например:

5 x 5 x 5 = 125 = 6n - 1

7 x 7 x 7 = 343 = 6n + 1

7 x 11 x 13 = 1001 = 6n + 1

Данные числа, расположенные в рядах простых чисел назовём исключениями. Исключения, расположенные в первом ряду простых чисел, находятся по формулам:

(6n - 1)(6k - 1)

(6n + 1)(6k + 1)

Расположенные  в пятом ряду по формуле:

(6n - 1)(6k + 1)

При этом поиск исключений простых чисел в первом ряду по формуле (6n - 1)(6k - 1) упрощается, так как исходное число всегда оканчивается на 5: 25, 55, 85, 115 и т. д..

Рассмотрим следующий пример:

Является ли число 77 простым? Определяем в каком ряду находится число 77. Оно находится в пятом ряду.

(6n - 1) = 77

6n = 78

n = 13

Далее проверяем, является ли оно исключением:

(6n - 1)(6k + 1) = 77

36nk + 6n - 1 = 77

36nk + 6n - 6k = 78

6 (6nk + n - k) = 78

6nk + n - k = 13

= 2, = 1

Число 77 не является простым числом.

Данные формулы удобны для поиска отдельных простых чисел.

Следующая формула позволит нам определить исключения из простых чисел на любом интервале рядов  простых чисел:

6na ± a

где n-натуральное число,

a- простое число.

Пример: n=1       a=5

6 x 1 x 5 ± 5 = 25; 35

n=1      a=7

6 x 1 x 7 ± 7 = 35; 49

n=1      a=11

6 x 1 x 11 ± 11 = 55; 77

и т.д.

При применении данной формулы в интервале от 0 до 1000,1000 и т.д. мы в несколько действий определим простые числа на данном отрезке.

Предложенные выше алгоритмы не направлены непосредственно на поиск простых чисел. Они показывают исключения, находя которые и определяются простые числа.