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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
EMBY
Заблокирован
#1

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

02.10.2012, 22:36. Просмотров 1353. Ответов 3
Метки нет (Все метки)

Здравствуйте!
Возникла проблемка с задачкой. Требуется вывести все простые числа от 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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2012, 22:36     Вывод простых чисел от m до n
Посмотрите здесь:

C++ Вывод всех простых чисел.
Массив целых чисел состоит из n элементов, найти сумму простых чисел, входящих в него C++
C++ Дана последовательность целых чисел а1, а2, …, an. Выяснить, является ли она симметричной последовательностью простых чисел
C++ Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?
Вывод простых чисел C++
Вывод простых чисел C++
C++ как вычислить количество простых чисел среди положительных чисел массива
C++ Вывод простых чисел из массива
Где ошибка, вывод простых чисел C++
C++ Вычислить количество простых чисел среди положительных чисел массива
C++ Вывод всех простых чисел в диапазоне от 1 до 100
Вывод простых чисел на заданном отрезке C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Астик
 Аватар для Астик
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
4661 / 2487 / 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
4218 / 2192 / 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
Ответ Создать тему
Опции темы

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