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

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

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

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

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

Под "мультипростым" числом понимается простое число, которое либо состоит из одной цифры (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++

{
  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

#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 мой код выдаёт, что оно мультипростое. См ссылку выше. А если внимательнее посмотреть обе ссылки, то вот:

Код

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, это лишь упростит перебор

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	03.12.2013, 01:22	25
	Сообщение от Di_ После проверки преподавателем, было снято два бала, за то что программа не правильно обрабатывает нули. Эм.. А как их надо обрабатывать? Про это в условии ничего не было. Вполне логично, что лидирующие нули на результат не влияют. 0

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

@easybudda Модератор 12458 / 7482 / 1753 Регистрация: 25.07.2009 Сообщений: 13,762
	03.12.2013, 18:20	28
	Сообщение от Di_ В любом случае, is_prime - это просто. Угу, только в вашем варианте ноль и один - тоже простые числа. Вам уже несколько реализаций функции is_prime() представили, где этой ошибки нет. Точно читаете, что пишут? Сообщение от Di_ и действительно, 22307 выдает не мультипрайм А не должно бы? 22 - уже не простое число, до нуля и дело не доходит. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	03.12.2013, 18:40	29
	Сообщение от easybudda 22 - уже не простое число, до нуля и дело не доходит 22307 = 223 * 7 (223 - простое, 7 - тоже) 223 = 2 * 23 23 = 2 * 3 Здесь * - операция "расщепления" чтобы число было мультипраймом достаточно существования одной серии расщеплений 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	03.12.2013, 19:04	32
	Сообщение от ПерС 22307 - ето 2 2 и 307, у меня так разложилось Не годится. Надо на 2 части, а не на 3. 22 307 - не подходит, т. к. 22 делится на 2. 2 2307 - не подходит, т. к. 2307 делится на 3. А из остального такие три куска не получатся. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	02.12.2013, 20:02	22
	ошибся таки Добавлено через 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 [ТС]	24
	После проверки преподавателем, было снято два бала, за то что программа не правильно обрабатывает нули. например, число 22307. Остальные замечания приняла к сведению. Qwertiy, к сожалению, прямо сейчас не могу просмотреть внимательно коды - надо на другие задачи переключаться. Но позже - обязательно. Спасибо 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	03.12.2013, 17:18	27
	Сообщение от Di_ говорят, что вылетает, если один ноль в числе Где что вылетает? Вот я беру свой код отсюда и всё работает на числах от 0 до 10000: http://codepad.org/cVMZS41g. Добавлено через 5 минут Сообщение от Di_ и действительно, 22307 выдает не мультипрайм Неправда: http://codepad.org/fzStjjF6. 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	03.12.2013, 18:43	30
	Сообщение от easybudda Угу, только в вашем варианте ноль и один - тоже простые числа. В моём ни 0, ни 1 простыми не являются. Но в качестве особого случая стоит что 1 - мультипростое (т. к. это несколько раз написано в теме, в том числе в стартовом посте. Сообщение от easybudda > и действительно, 22307 выдает не мультипрайм А не должно бы? 22 - уже не простое число, до нуля и дело не доходит. Ещё раз. Неправда, на 22307 мой код выдаёт, что оно мультипростое. См ссылку выше. А если внимательнее посмотреть обе ссылки, то вот: Код 22307 as 223 07 223 as 2 23 2 as 2 23 as 2 3 2 as 2 3 as 3 7 as 7 0

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

@ПерС 585 / 488 / 371 Регистрация: 05.11.2013 Сообщений: 1,265 Записей в блоге: 6
	03.12.2013, 19:15	33
	ну, я изначально предполагал любое число составляющих, а не 2, опираясь на условие простое число, которое либо состоит из одной цифры (3, 5...), либо которое можно разбить на простые и/или мультипростые составляющие впрочем, если частей обязано быть 2, это лишь упростит перебор 0