проверка на мультипростое число

@Di_ · Регистрация: 27.11.2013

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

Доброго времени суток!
Попыталась найти что-то подобное на форуме - не нашла (очень сложно сформулировать поисковый запрос по проблеме).
Сама уже вторые сутки ломаю голову (понимаю, что не срок. Однако препод бьет копытом, брызжет слюной и ругается).

Задача
Требуется написать программу, которое будет выводить, является ли введенное с клавиатуры число "мультипростым".

Под "мультипростым" числом понимается простое число, которое либо состоит из одной цифры (3, 5...), либо которое можно разбить на простые и/или мультипростые составляющие. Под разбивкой понимается отделение скольких бы то ни было левых цифр числа от остальных.
Сложно объяснить, проще показать на примере:
Число 7523.
Само по себе число 7523 простое.
Возможны три варианта разбивки:
7 523
75 23
752 3
7 - простое число.
523 - тоже просто и может быть разбито на 5 23 или 52 3. Пять - простое число. Двадцать три - тоже, причем, два и три - тоже простые.
Т.е. возможен как минимум один вариант, что это число "мультипростое" => тру.

Программа должна обязательно содержать две функции:
нерекурсивную int is_prime(int num) (которая возвращает 1, если число простое, и 0 - в обратном случае)
и рекурсивную int is_multi_prime(int num) (которая возвращает 1, если число "мультипростое", и 0 - в обратном случае).
Если кому нужно, я могу выслать оригинал задания (на английском языке).
Ко всему прочему, есть ограничения, установленные преподавателем: "вы должны использовать только то, что мы уже прошли на занятиях. и ни в коем случае то, что мы еще не прошли".
Так что массивы, строки, классы - использовать нельзя. По сути, можно использовать только функции и рекурсию.

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

C++
1
2
3
4
5
6
7
8
9
{
  int i;
  for( i=2; i*i<=num; i++)
  {
    if (num%i ==0) 
      return 0;
  }
  return 1;
}

Также, я еще создала функцию, которая считает количество цифр в введенном числе.
Она используется в дальнейшем для разделения числа.
Если мы хотим отделить первое число, то
num1 = num\10^(n-1) - первая цифра ("7" в примере)
num2 = num%10^(n-1) - все остальное("523" в примере)

на входе функция is_multi_prime в первую очередь проверяет целое ли введенное число вообще (если нет, значит сразу же 0), потом разделяет его по первой цифре. Если первая цифра - прайм, то функция рекурсивно вызывается опять с параметром num2.

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

Более того, я ни малейшего понятия не имею, как запихнуть проверку следующего разделения, если первое не прошло (например, 2311 - простое число. два - не простое, но 23 и 11 - простые, 2 и 3, 1 и 1 - простые). Ну в смысле, я могу русским/английским языком описать алгоритм, но не могу его описать на Си.

З.ы,
Думаю, меня вполне устроит подробный алгоритм на русском/английском, но если будет разобранный код - будет лучше.
Также, могу скинуть скетч блок-схемы, конкретно лекции/семинары по курсу и т.п.

Спасибо!!

ValeryS · 02.12.2013, 19:59

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

Не вижу выигрыша от этого.

ну я не знаю

вижу два прототипа функции

C
1
int is_prime(int num)

и

C++
1
bool is_prime(int num)

где более понятна логика?

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

Это раздел по Си, так что bool не существует.

перепутал форум

бывает

Байт · 02.12.2013, 20:02

ошибся таки

Добавлено через 47 секунд
1 2 3 5 7 - Мультипростые.
Если простое число X можно представить в виде K*10ⁿ + M, где M < 10ⁿ, K, M - мультипростые, то X - мультипростое

@Qwertiy · 02.12.2013, 20:10

Исправленный код:

C
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
 
int is_prime(unsigned x)
  {
  unsigned q;
 
  if(!(x&1))
    return x==2;
 
  if(x==1)
    return 0;
 
  for(q=3; q*q<=x; q+=2)
    if(!(x%q))
      return 0;
 
  return 1;
  }
 
unsigned is_multiprime(unsigned x)
  {
  unsigned q;
 
  if(!is_prime(x))
    return x==1;
 
  if(x<10)
    return 1;
 
  for(q=10; q<x; q*=10)
    if(is_multiprime(x/q) && is_multiprime(x%q))
      return q;
 
  return 0;
  }
 
int digits(unsigned x)
  {
  unsigned res;
 
  for(res=0; x; ++res)
    x/=10;
  
  return res;
  }
 
int main(void)
  {
  unsigned q, base;
 
  for(q=0; q<10000; ++q)
    if(base=is_multiprime(q) /*assignment*/)
      printf("%d as %d %.*d\n", q, q/base, digits(base-1), q%base);
 
  puts("Done.");
  getchar();
  return 0;
  }

Добавлено через 7 минут

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

C
1
printf("%d as %d %.*d\n", q, q/base, digits(base-1), q%base);

Хм.. Наверное, так правильнее:

C
1
printf("%d as %d %00.*d\n", q, q/base, digits(base-1), q%base);

А может и нет...

@Di_ · 03.12.2013, 00:41 **[ТС]**

После проверки преподавателем, было снято два бала, за то что программа не правильно обрабатывает нули.
например, число 22307.

Остальные замечания приняла к сведению.

Qwertiy, к сожалению, прямо сейчас не могу просмотреть внимательно коды - надо на другие задачи переключаться.
Но позже - обязательно.
Спасибо

@Qwertiy · 03.12.2013, 01:22

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

После проверки преподавателем, было снято два бала, за то что программа не правильно обрабатывает нули.

Эм.. А как их надо обрабатывать? Про это в условии ничего не было. Вполне логично, что лидирующие нули на результат не влияют.

@Di_ · 03.12.2013, 15:17 **[ТС]**

Qwertiy, говорят, что вылетает, если один ноль в числе

__
и действительно, 22307 выдает не мультипрайм

@Qwertiy · 03.12.2013, 17:18

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

говорят, что вылетает, если один ноль в числе

Где что вылетает?
Вот я беру свой код отсюда и всё работает на числах от 0 до 10000: http://codepad.org/cVMZS41g.

Добавлено через 5 минут

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

и действительно, 22307 выдает не мультипрайм

Неправда: http://codepad.org/fzStjjF6.

@easybudda · 03.12.2013, 18:20

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

В любом случае, is_prime - это просто.

Угу, только в вашем варианте ноль и один - тоже простые числа. Вам уже несколько реализаций функции is_prime() представили, где этой ошибки нет. Точно читаете, что пишут?

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

и действительно, 22307 выдает не мультипрайм

А не должно бы? 22 - уже не простое число, до нуля и дело не доходит.

Байт · 03.12.2013, 18:40

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

22 - уже не простое число, до нуля и дело не доходит

22307 = 223 * 7 (223 - простое, 7 - тоже)
223 = 2 * 23
23 = 2 * 3
Здесь * - операция "расщепления"
чтобы число было мультипраймом достаточно существования одной серии расщеплений

@Qwertiy · 03.12.2013, 18:43

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

Угу, только в вашем варианте ноль и один - тоже простые числа.

В моём ни 0, ни 1 простыми не являются. Но в качестве особого случая стоит что 1 - мультипростое (т. к. это несколько раз написано в теме, в том числе в стартовом посте.

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

> и действительно, 22307 выдает не мультипрайм
А не должно бы? 22 - уже не простое число, до нуля и дело не доходит.

Ещё раз. Неправда, на 22307 мой код выдаёт, что оно мультипростое. См ссылку выше. А если внимательнее посмотреть обе ссылки, то вот:

Code
1
2
3
4
5
6
7
22307 as 223 07
  223 as 2 23
    2 as 2
    23 as 2 3
      2 as 2 
      3 as 3 
  7 as 7

@ПерС · 03.12.2013, 18:59

Упс, всё ещё ёжите мультипростые числа?

22307 - ето 2 2 и 307, у меня так разложилось

@Qwertiy · 03.12.2013, 19:04

Сообщение от ПерС

22307 - ето 2 2 и 307, у меня так разложилось

Не годится. Надо на 2 части, а не на 3.
22 307 - не подходит, т. к. 22 делится на 2.
2 2307 - не подходит, т. к. 2307 делится на 3.
А из остального такие три куска не получатся.

@ПерС · 03.12.2013, 19:15

ну, я изначально предполагал любое число составляющих, а не 2, опираясь на условие

простое число, которое либо состоит из одной цифры (3, 5...), либо которое можно разбить на простые и/или мультипростые составляющие

впрочем, если частей обязано быть 2, это лишь упростит перебор

Новые блоги и статьи Все статьи Все блоги /
Жара жесть. kumehtar 18.08.2026 Пролетают летом дни Тридцать пять жары в тени. Каждый август год от года Дарит жаркую погоду.	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	02.12.2013, 20:02
	ошибся таки Добавлено через 47 секунд 1 2 3 5 7 - Мультипростые. Если простое число X можно представить в виде K*10ⁿ + M, где M < 10ⁿ, K, M - мультипростые, то X - мультипростое 0

@Di_ 13 / 2 / 0 Регистрация: 27.11.2013 Сообщений: 9
	03.12.2013, 00:41 [ТС]
	После проверки преподавателем, было снято два бала, за то что программа не правильно обрабатывает нули. например, число 22307. Остальные замечания приняла к сведению. Qwertiy, к сожалению, прямо сейчас не могу просмотреть внимательно коды - надо на другие задачи переключаться. Но позже - обязательно. Спасибо 0

@Di_ 13 / 2 / 0 Регистрация: 27.11.2013 Сообщений: 9
	03.12.2013, 15:17 [ТС]
	Qwertiy, говорят, что вылетает, если один ноль в числе __ и действительно, 22307 выдает не мультипрайм 0

@ПерС 587 / 490 / 371 Регистрация: 05.11.2013 Сообщений: 1,272 Записей в блоге: 6
	03.12.2013, 18:59
	Упс, всё ещё ёжите мультипростые числа? 22307 - ето 2 2 и 307, у меня так разложилось 0