БлогNot. Мультипростые числа

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

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

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

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

Замечания:

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

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


теги: числа алгоритм c++

29.11.2013, 16:36; рейтинг: 8701

  свежие записипоиск по блогукомментариистатистика

Наверх Яндекс.Метрика
© PerS
вход