Форум программистов, компьютерный форум, киберфорум
ПерС
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Мультипростота

Запись от ПерС размещена 28.11.2013 в 15:30
Обновил(-а) ПерС 30.11.2013 в 17:08

Любопытной показалась задача:
Цитата:
Требуется написать программу, которое будет выводить, является ли введенное с клавиатуры число "мультипростым".

Под "мультипростым" числом понимается простое число, которое либо состоит из одной цифры (3, 5...), либо которое можно разбить на простые и/или мультипростые составляющие. Под разбивкой понимается отделение скольких бы то ни было левых цифр числа от остальных.
Пример: 7523 - да, ибо 7, 5, 2 и 3 (или 7, 5 и 23, или 7 и 523)

Вот "переборное" решение :

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
//Для отладочной печати
long int *stack;
int size;
 
void init_stack (unsigned long int n) {
 char s[20];
 ultoa (n,s,10);
 int len=strlen(s);
 stack=(long int *)calloc(len+1,sizeof(long int));
 size=0;
}
 
void push_stack (long int n) { stack[size++]=n; }
 
void clear_stack () { size=0; }
 
void print_stack (unsigned long int n) {
 printf ("\n%lu: ",n);
 int i;
 for (i=0; i<size; i++) printf (" %ld",stack[i]);
}
 
//Решение
int is_simple (unsigned long int n) {
 unsigned long int i;
 int r=1;
 if (n<2) r=0;
 else if (n==2) r=1;
 else if (n%2==0) r=0;
 else if (n<6) r=1;
 else for (i=3; i<=floor(sqrt(n)); i++) if (n%i==0) { r=0; break; }
 return r;
}
 
int is_multi_simple (unsigned long int n) {
 char s[20],c1[20],c2[20];
 long int n1,n2;
 int i,j,len,sn1,sn2,msn1,msn2;
 ultoa (n,s,10);
 len=strlen(s);
 if (len<2) {
  i=is_simple(n);
  if (!i) clear_stack();
  return i;
 }
 for (i=1; i<len; i++) {
  strncpy(c1,s,i);
  c1[i]='\0';
  n1=atol(c1);
  strncpy(c2,&s[i],len-i);
  c2[len-i]='\0';
  n2=atol(c2);
  //printf ("%ld,%ld ",n1,n2);
  sn1=is_simple(n1);
  sn2=is_simple(n2);
  if (!sn1 && !sn2) continue;
  if (sn1) push_stack(n1);
  if (sn2) push_stack(n2);
  if (sn1 && sn2) return 1;
  if (!sn1) msn1=is_multi_simple(n1); else msn1=0;
  if (!sn2) msn2=is_multi_simple(n2); else msn2=0;
  if (sn1 && msn2 || msn1 && sn2 || msn1 && msn2) return 1;
 }
 clear_stack();
 return 0;
}
 
int main () {
 unsigned long int i,n=100; //n - граница поиска
 init_stack (n);
 for (i=1; i<=n; i++) {
  clear_stack();
  if (is_simple (i)) if (is_multi_simple (i)) print_stack (i);
 }
 printf ("\nENTER to exit");
 getchar();
 return 0;
}
Замечания:
  • Следует помнить, что число 1 - не простое, а 2 - по определению, да.
  • По определению, нули не учитываются, так, число 5003 - мультипростое, раскладывается на 5 и 3;
  • Найдётся всегда первое из возможных разбиений числа (для 7523 - 7 и 523);
  • Это хороший, годный пример на рекурсию.

В первой сотне нашлось всего 8 мультипростых чисел.

Цитата:
2:
3:
5:
7:
23: 2 3
37: 3 7
53: 5 3
73: 7 3
Размещено в Без категории
Показов 1862 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru