Форум программистов, компьютерный форум CyberForum.ru

Вывод простых чисел от m до n - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
EMBY
Заблокирован
02.10.2012, 22:36     Вывод простых чисел от m до n #1
Здравствуйте!
Возникла проблемка с задачкой. Требуется вывести все простые числа от m до n, при условии, что 2<=m<=n<=1000000. Если нет простых, то вывести "Absent". Время 6 с.
1 проблема заключается в выводе "Absent". Почему-то, она его либо не выводит(если m=n),либо(если n не простое) она пишет все простые числа от m до n и вместо n пишет "Absent".
2 проблема заключается во времени выполнения программы, если числа больше 10000, то она уже перескакивает ограничение по времени. Я могу попробовать сделать через массив, но мне надо именно без него. Подскажите, что делать. Буду благодарен!
Вот код:
C++ (Qt)
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
#include "stdafx.h"
#include <stdio.h>
#include <clocale>
#include <math.h>
 
 
int _tmain(int argc, _TCHAR* argv[])
{  
 setlocale(LC_ALL,"RUSSIAN");
 setlocale(LC_ALL,"rus");
 
 
 
 long  c,m,i,n,d=0;
 long  del=0;
 bool prostota;
 printf("Программа для вывод всех простых чисел от M до N включитально\n");
 
//Начальная инициализация
 printf("Введите 2 простых числа\n");
 scanf("%d", &m);
 scanf("%d", &n);
 
//Решение
 for(i=m; i<=n;i++)
 {   
     prostota=true;
     for (del=2; del<=ceil( sqrt ((float)i));del++)
     {if (i%del==0 && i!=del)
     {
      prostota=false;
      break;
     }
     }
     if(prostota && m!=n)
     {
     printf("%d\n",i);
     }
    
 } if(!prostota && m!=n )
   printf("absent\n");
     
 
 getchar();
 getchar();
 return 0;
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Астик
 Аватар для Астик
11 / 11 / 0
Регистрация: 03.10.2010
Сообщений: 173
Записей в блоге: 1
03.10.2012, 02:40     Вывод простых чисел от m до n #2
вот ты с условиями немного запутался... вроде получается
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
#include <stdio.h>
#include <clocale>
#include <math.h>
#include <conio.h>
 
 
 
 int main()
{  
 setlocale(LC_ALL,"RUSSIAN");
 setlocale(LC_ALL,"rus");
 
 
 
 long  c,m,i,n,d=0;
 long  del=0;
 bool prostota;
 printf("Программа для вывод всех простых чисел от M до N включитально\n");
 
//Начальная инициализация
 printf("Введите 2 простых числа\n");
 scanf("%d", &m);
 scanf("%d", &n);
 
//Решение
 for(i=m; i<=n;i++)
 {   
     prostota=true;
     for (del=2; del<=ceil( sqrt ((float)i));del++)
         if (i%del==0 && i!=del)
         {
             prostota=false;
             break;
         }
    
     if(prostota && m!=n)
     {
     printf("%d\n",i);
     }
 }
      if(prostota )
          printf("absent\n");
 
 getch();
 
 return 0;
}
а на счет второго пункта не понял... ввожу 11000 и 12000 вычисляет за сек )!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.10.2012, 03:44     Вывод простых чисел от m до n #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Астик, все равно не правильно. Значение переменной prostota будет зависеть от последнего числа (простое или нет последнее число n).

EMBY, тут недавно была тема:
Быстрая проверка натурального числа на простоту
даже при использовании первого способа программа укладывается в 6 сек с большим запасом.
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
#include <stdio.h>
#include <clocale>
#include <math.h>
#include <conio.h>
 int Prime(int a)
{
   int i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}
 
 
 int main()
{  
 setlocale(LC_ALL,"RUSSIAN");
 setlocale(LC_ALL,"rus");
 
 
 
 long  c,m,i,n,d=0;
 long  del=0;
 bool prostota=true;
 printf("Программа для вывод всех простых чисел от M до N включитально\n");
 
//Начальная инициализация
 printf("Введите 2 простых числа\n");
 scanf("%d", &m);
 scanf("%d", &n);
 
//Решение
 for(i=m; i<=n;i++)
 {   
     if(Prime(i))
     {
          printf("%d\n",i);
          prostota=false;
     }
     
 }
      if(prostota )
          printf("absent\n");
 
 getch();
 
 return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.10.2012, 08:25     Вывод простых чисел от m до n #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
тут недавно была тема

Не по теме:

плохо, что при увеличении числа m алгоритм не становится быстрее, а наоборот. а ведь по логике вещей, чем ближе число m=2*3*5*... к корню из исследуемого числа, тем больше убираются из рассмотрения ненужных делителей, вплоть до всех составных делителей. путь оказался тупиковым (так как при использовании массивов вся скорость сходит на нет), разве что при m=30 алгоритм неплохой получился. а больше способов нет, которые используют ограниченную память при неограниченных тестируемых числах.

Yandex
Объявления
03.10.2012, 08:25     Вывод простых чисел от m до n
Ответ Создать тему
Опции темы

Текущее время: 03:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru