Мультипростые числа

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

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

Пример: 7523 - да, ибо 7, 5, 2 и 3 (или 7, 5 и 23, или 7 и 523 и т.д.)

Вот несложное решение, перебирающее заданный диапазон чисел от 1 до n включительно.

#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 и 003=3;
• Найдётся всегда первое из возможных разбиений числа (для 7523 - 7 и 523, для 1153 - 11 и 53);
• Это хороший, годный пример на рекурсию.

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

2:
3: 
5: 
7: 
23:  2 3
37:  3 7
53:  5 3
73:  7 3

29.11.2013, 16:36 [10006 просмотров]