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

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

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

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

02.10.2012, 22:36. Просмотров 1441. Ответов 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;
}
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2012, 22:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывод простых чисел от m до n (C++):

Вывод простых чисел - C++
задали задачу написать ряд простых чисел,у самого мозгов не хватило толком ее написать,написал с миру по нитке,без ввода с клавиатуры с...

Вывод простых чисел - C++
Всем привет, люди помогите написать программу очень нужно и если можно то с комментариями. Написать программу, которая выводит простые...

Вывод всех простых чисел. - C++
Задали задачку. Вывести все простые числа от 1 до n Примерно сделал на паскале. До 100 все работает а дальше он не может ворочать...

Вывод простых чисел из массива - C++
здравствуйте. я в интернете нашел программу которая выбирает простые числа из массива, но до сих пор не могу понять что такое &quot;...

Вывод простых чисел на заданном отрезке - C++
Поделитесь мыслью, как это сделать. В теории о том, каким образом искать простое число ничего не говорится а также подскажите каким образом...

Где ошибка, вывод простых чисел - C++
for ( int i = 2; i * i &lt;= n; i++ ) { if ( n % i == 0 ) { return 0; } } ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Астик
12 / 12 / 0
Регистрация: 03.10.2010
Сообщений: 173
Записей в блоге: 1
03.10.2012, 02:40 #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 вычисляет за сек )!
1
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.10.2012, 03:44 #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;
}
3
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.10.2012, 08:25 #4
Цитата Сообщение от valeriikozlov Посмотреть сообщение
тут недавно была тема

Не по теме:

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

1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2012, 08:25
Привет! Вот еще темы с ответами:

Вывод всех простых чисел в диапазоне от 1 до 100 - C++
Написать функцию, определяющую, является ли введенное целое чис- ло простым или нет. (Число простое, если оно делится только на 1 и на...

Вычислить количество простых чисел среди положительных чисел массива - C++
Дан массив целых положительных и отрицательных чисел в количестве меньше или равно 64 . А требуется , Вычислить количество простых чисел...

Дан массив целых чисел. Верно ли, что он состоит только из простых чисел? - C++
Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?

Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел последовательности - C++
Использовать функции в программе Задание: Вводится последовательность целых чисел. Определить среднее арифметическое простых чисел...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.10.2012, 08:25
Ответ Создать тему
Опции темы

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