Простые ли числа 31, 331, 3331, 33331,

echs · Регистрация: 23.10.2013

Студворк — интернет-сервис помощи студентам

Требуется решить задачу. Являются ли числа вида 33...31
простыми? Программа выявила, что числа 31, 331,
3331, 33331, 333331, 3333331, 33333331 - простые.
а вот число 333333331 - оказалось составным. А как дальше?
бейсик не очень любит возиться с длинными числами...

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
REM   
REM  31, 331, 3331, ... , 33333331
REM  333333331 - составное число
REM
 
CLS
DIM p AS LONG
DIM p2 AS LONG
 
p = 31
 
DO
   p2 = SQR(p)
  
   FOR d = 7 TO p2
      IF p MOD d = 0 THEN 100
   NEXT
   PRINT p
   p = 10 * p + 21
   GOTO 200
100
   PRINT p; "***"
   IF p > 300000000 THEN EXIT DO
   p = 10 * p + 21
200
LOOP WHILE p < 400000000
END

@Sasha_Smirnov · 30.07.2016, 22:49

Онлайн 1 человек (ваш покорный)… видимо, QBasic в быту вообще неудобен (несмотря на педагогические заслуги).

Среди чисел вида (3)…1 многие простые: 18 знаков, 40, 50, 60… дальше смотреть не на чем.

numberempire.com/factoringcalculator.php?function=3333333333333333333333333333333333333331

@volvo · 30.07.2016, 23:03

Здесь есть больше простых чисел этого типа: Factorization of 33...331

@Sasha_Smirnov · 31.07.2016, 03:12

Не менее красива и факторизация (2)…1 — изыскания начала века* (2003 и 2004 гг.): http://stdkmd.com/nrr/2/22221.... otfactored!

Сообщение от geh

бейсик не очень любит возиться с длинными числами...

Уважаемый geh, тем не менее 29-значные он худо-бедно переваривает (в VBA-приложениях): Вывод делителей натурального числа (2013)! Но ждать даже и несколько секунд… не те времена!
____________________
* И вот тоже («в домашних условиях» на ВБА): Теория чисел: печать простых делителей (2009, кустарщина!)

@m-ch · 31.07.2016, 10:22

код на VBA:

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Sub test()
    Dim i&, m$, t!
    t = Timer
    For i = 1 To 24
        m = String$(i, "3") & 1
        Debug.Print m & " = " & PrimeFact(m)
    Next i
    Debug.Print Timer - t
End Sub
 
Function PrimeFact$(m$)
    Dim i&, txt$, n
    n = CDec(m)
    If n < 4 Then
        PrimeFact = "Prime"
        Exit Function
    End If
    i = 3
    While Fix(n / 2) = n / 2
        n = Fix(n / 2)
        txt = txt & "*2"
    Wend
    While CDec(i) * i <= n
        If Fix(n / i) <> n / i Then i = i + 2 Else n = Fix(n / i): txt = txt & "*" & i
    Wend
    If n > 1 Then txt = txt & "*" & n
    If InStr(2, txt, "*") Then PrimeFact = Mid$(txt, 2) Else PrimeFact = "Prime"
End Function

Считал 6 минут от двухзначного до 25-значного числа

Кликните здесь для просмотра всего текста

31 = Prime
331 = Prime
3331 = Prime
33331 = Prime
333331 = Prime
3333331 = Prime
33333331 = Prime
333333331 = 17*19607843
3333333331 = 673*4952947
33333333331 = 307*108577633
333333333331 = 19*83*211371803
3333333333331 = 523*3049*2090353
33333333333331 = 607*1511*1997*18199
333333333333331 = 181*1841620626151
3333333333333331 = 199*16750418760469
33333333333333331 = 31*1499*717324094199
333333333333333331 = Prime
3333333333333333331 = 1009*1303427*2534550017
33333333333333333331 = 29*29*1039*3389*11256299321
333333333333333333331 = 23*164844923*87917500639
3333333333333333333331 = 177943*18732590398798117
33333333333333333333331 = 61*179*241049*12664572810301
333333333333333333333331 = 312929*2228959*477893202221
3333333333333333333333331 = 17*821593951*238656128290493

Добавлено через 52 минуты
Для бОльших чисел переменную i в функции PrimeFact нужно объявить As Double а не As Long
Это скажется на скорости вычислений, но позволит считать и далее не вызывая переполнения переменной.

@Sasha_Smirnov · 31.07.2016, 10:23

У меня 8 минут (Word):

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
31 = Prime
331 = Prime
3331 = Prime
33331 = Prime
333331 = Prime
3333331 = Prime
33333331 = Prime
333333331 = 17*19607843
3333333331 = 673*4952947
33333333331 = 307*108577633
333333333331 = 19*83*211371803
3333333333331 = 523*3049*2090353
33333333333331 = 607*1511*1997*18199
333333333333331 = 181*1841620626151
3333333333333331 = 199*16750418760469
33333333333333331 = 31*1499*717324094199
333333333333333331 = Prime
3333333333333333331 = 1009*1303427*2534550017
33333333333333333331 = 29*29*1039*3389*11256299321
333333333333333333331 = 23*164844923*87917500639
3333333333333333333331 = 177943*18732590398798117
33333333333333333333331 = 61*179*241049*12664572810301
333333333333333333333331 = 312929*2228959*477893202221
3333333333333333333333331 = 17*821593951*238656128290493
 505,3555

Загрузка ЦП была при этом около 30%, а частота примерно 2,5 ГГц.

@m-ch · 31.07.2016, 10:40

Сообщение от Sasha_Smirnov

Загрузка ЦП была при этом около 30%, а частота примерно 2,5 ГГц

VBA задействует только одно ядро процессора, поэтому загрузка только 30%
у меня i7-3630QM 2.4GHz, считал чуть более 6 минут

@m-ch · 31.07.2016, 13:32

на FreeBasic вычисления от 2х до 19ти значных чисел - менее трех секунд
Далее не хватает разрядности у 8ми байтового целого числа:

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
FUNCTION PrimeFact(BYVAL n AS ULongInt) AS STRING
    DIM i AS ULongInt, txt AS STRING
    IF n < 4 THEN
        PrimeFact = "Prime"
        EXIT FUNCTION
    END IF
    i = 3
    WHILE n = (n \ 2) * 2 
        n = n \ 2
    txt = txt & "*2"
    WEND
    WHILE i * i <= n
        IF n > (n \ i) * i THEN i = i + 2 ELSE n = n \ i: txt = txt & "*" & i
    WEND
    IF n > 1 THEN txt = txt & "*" & n
    IF INSTR(2, txt, "*") THEN PrimeFact = MID$(txt, 2) ELSE PrimeFact = "Prime"
END FUNCTION
 
DIM i AS LONG, n AS ULongInt, t AS DOUBLE
t = TIMER
FOR i = 1 TO 18
    n = ValULng(STRING$(i,"3") & "1")
    PRINT n, PrimeFact(n)
NEXT i
PRINT TIMER - t
SLEEP

echs · 31.07.2016, 16:59 **[ТС]**

Я тоже написал программу для вычисления простых
чисел длинной до 18 знаков. Но она не представляет
большого практического интереса. Ибо при длине числа
более 10 знаков тратит много времени. Ведь это qbasic!

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DECLARE FUNCTION N! (i!)
CLS
DIM SHARED sp AS STRING
DIM p AS LONG
DIM d AS LONG
DIM p2 AS LONG
 
sp = "33333331"
p2 = SQR(VAL(sp))
  
FOR d = 7 TO p2
   p = 0
   FOR i = 1 TO LEN(sp)
      p = 10 * p + N(i)
      p = p MOD d
   NEXT i
   IF p = 0 THEN 100
NEXT d
PRINT sp
100
END
 
FUNCTION N (i)
   N = VAL(MID$(sp, i, 1))
END FUNCTION

@Sasha_Smirnov · 26.12.2016, 03:03

На базе Excel

Сообщение от m-ch

код на VBA

нашёл 25-значное число на 56 секунд быстрее:

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
31 = Prime
331 = Prime
3331 = Prime
33331 = Prime
333331 = Prime
3333331 = Prime
33333331 = Prime
333333331 = 17*19607843
3333333331 = 673*4952947
33333333331 = 307*108577633
333333333331 = 19*83*211371803
3333333333331 = 523*3049*2090353
33333333333331 = 607*1511*1997*18199
333333333333331 = 181*1841620626151
3333333333333331 = 199*16750418760469
33333333333333331 = 31*1499*717324094199
333333333333333331 = Prime
3333333333333333331 = 1009*1303427*2534550017
33333333333333333331 = 29*29*1039*3389*11256299321
333333333333333333331 = 23*164844923*87917500639
3333333333333333333331 = 177943*18732590398798117
33333333333333333333331 = 61*179*241049*12664572810301
333333333333333333333331 = 312929*2228959*477893202221
3333333333333333333333331 = 17*821593951*238656128290493
 449,207

Я сейчас запустил этот

Сообщение от m-ch

Visual Basic
1
Sub test()

(уже забыв, о чём это), а на ноутбуке Control-Break не сделать… и следил по диспетчеру: «А чего это он тут делает?»!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

Простые ли числа 31, 331, 3331, 33331,

Решение

Решение

Решение

@Sasha_Smirnov 5562 / 1370 / 150 Регистрация: 08.02.2009 Сообщений: 4,109 Записей в блоге: 30
	30.07.2016, 22:49
	Онлайн 1 человек (ваш покорный)… видимо, QBasic в быту вообще неудобен (несмотря на педагогические заслуги). Среди чисел вида (3)…1 многие простые: 18 знаков, 40, 50, 60… дальше смотреть не на чем. numberempire.com/factoringcalculator.php?function=3333333333333333333333333333333333333331 1

@volvo Супер-модератор 33398 / 21508 / 8236 Регистрация: 22.10.2011 Сообщений: 36,904 Записей в блоге: 12
	30.07.2016, 23:03
	Здесь есть больше простых чисел этого типа: Factorization of 33...331 2