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

Найти все простые числа на отрезке [a,b]. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.67
DieZZzz
0 / 0 / 0
Регистрация: 29.09.2011
Сообщений: 29
02.10.2011, 22:44     Найти все простые числа на отрезке [a,b]. #1
Изучаем C++ месяц. Сейчас сидим на циклах. Условие задачи, собственно, и есть название темы. К сожалению, справиться с ней у меня не получается. Нашел только в гугле программу которая выводит простые числа в интервале от 1 до 100, но там присутствуют операторы, которых мы еще не изучали. Вообщем, буду очень признателен, если кто-нибудь поможет с решением задачи.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xAtom
 Аватар для xAtom
910 / 735 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
03.10.2011, 02:20     Найти все простые числа на отрезке [a,b]. #2
Цитата Сообщение от DieZZzz Посмотреть сообщение
простые числа в интервале от 1 до 100
DieZZzz, вот держи надеюсь поймёшь.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int  main(void) {
   int a = 1;
   int b = 100;     
                        
   for(int i = a; i <= b; i++) {  // отрезок a <= b
         for(int j = 2; j <= i && (i % j); j++);
         if(j == i) 
              printf("%d, ", i);
    }
 
    getchar();
    return 0;
}
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
03.10.2011, 04:45     Найти все простые числа на отрезке [a,b]. #3
на верхней границе в 400 000 принудительно снимается с выполнения, на 350 000 работает

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
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
 
int prim_check(int *arr, const int end, int number){
    int i = 0;
    for(i; i < end; ++i)
        if (!(number % arr[i]))
            return 0;
    return 1;
}
 
int check_error(int *num){
    if(!num){
        printf("error of memory");
        exit(1);
    }
}
 
void print_array(int *arr, const int beg, const int count){
    int i;
    for (i = 0; i < count; ++i){
        if (arr[i] > beg)
            printf(" %d", arr[i]);
        if (!(i % 15))
            printf("\n");
    }
}
 
int main(){
    int *array = NULL, *tmp = NULL, i, count = 2, begin, end;
 
    array = (int*) malloc(count * sizeof(int));
    check_error(array);
    array[0] = 2; array[1] = 3;
 
    printf("\n\n");
    printf("введите начало интервала:\n");
    scanf("%d", &begin);
    printf("введите конец интервала:\n");
    scanf("%d", &end);
 
    for(i = 5; i < end; i +=2)
        if(prim_check(array, count, i)){
            ++count;
            tmp = (int*)realloc(array, count * sizeof(int));
            check_error(tmp);
            tmp = NULL;
            array[count - 1] = i;
        }
 
    printf("простые числа в промежутке от %d до %d\n\n", begin, end);
    print_array(array, begin, count);
    printf("\n\n");
 
    free(array);
    return 0;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.10.2011, 16:17     Найти все простые числа на отрезке [a,b]. #4
Мое решение этой задачи...
2е место в топе.
Но для понимания сложновато...)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <fstream>
 
int a['   '], b, n, m, i = 1, j;
 
int main() {
    std::fstream v("input.txt"), o("output.txt", std::ios::out);
    for (v >> m >> n; i++ < n;  )
        if (!a[i])
        {
            for (j = i; j <= n; j += i)
                a[j] = 1;
            i < m || i > n ? 0 : (o << i << ' ', b = 1);
        }
    b ? !o : 
        o << "Absent";
}
DieZZzz
0 / 0 / 0
Регистрация: 29.09.2011
Сообщений: 29
03.10.2011, 17:09  [ТС]     Найти все простые числа на отрезке [a,b]. #5
Спасибо большое. А не расскажете, что за оператор такой bool term? А то я встретил его в одной из задач на нахождение простых чисел.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
03.10.2011, 20:09     Найти все простые числа на отрезке [a,b]. #6
DieZZzz, bool - логический тип данных. term - идентификатор, имя логической переменной, заданное программистом. Семантика та же, что и
C++
1
int a;
DieZZzz
0 / 0 / 0
Регистрация: 29.09.2011
Сообщений: 29
03.10.2011, 21:12  [ТС]     Найти все простые числа на отрезке [a,b]. #7
Цитата Сообщение от silent_1991 Посмотреть сообщение
DieZZzz, bool - логический тип данных. term - идентификатор, имя логической переменной, заданное программистом. Семантика та же, что и
C++
1
int a;
Т.е. переменные типа bool можут принимать значения либо true, либо false?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
03.10.2011, 21:20     Найти все простые числа на отрезке [a,b]. #8
DieZZzz, да.
LosAngeles
Заблокирован
07.10.2011, 12:15     Найти все простые числа на отрезке [a,b]. #9
фокус-покус!
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
 
 
template<int x, int y> struct isDelimeter 
{ 
    static const bool value = x % y != 0 && isDelimeter<x, y-1>::value; 
};
 
 
template<int x> struct isDelimeter<x, 1> 
{ 
    static const bool value = 1;
};
 
 
template<int x> struct isPrime 
{ 
    static const bool Yes = isDelimeter<x, x-1>::value;
};
 
template<> struct isPrime<1>
{
    static const bool Yes = true;
};
 
template<> struct isPrime<0>
{
    static const bool Yes = false;
};
 
 
template <int x, bool y = isPrime<x>::Yes > struct OutputAllPrimes;
 
 
template <int x> struct OutputAllPrimes<x, true>
{
    OutputAllPrimes() 
    {
        cout << x << " is prime!" << endl;
        OutputAllPrimes<x-1>();
    };
};
 
 
template <int x> struct OutputAllPrimes<x, false>
{
    OutputAllPrimes() 
    {
        OutputAllPrimes<x-1>();
    };
};
 
 
template <> struct OutputAllPrimes<1, true>
{
 
};
 
template <> struct OutputAllPrimes<1, false>
{
 
};
 
 
int main()
{
    OutputAllPrimes<30>();
 
 
    system("pause");
 
    return 0;
}
всё compile-time))
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
07.10.2011, 12:54     Найти все простые числа на отрезке [a,b]. #10
LosAngeles, разве 45 строка не сводит весь compile-time на нет?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2011, 13:58     Найти все простые числа на отрезке [a,b].
Еще ссылки по теме:

C++ Найти все простые числа, не превосходящие заданного N >0
C++ Найти все простые трёхзначные числа
На отрезке [2, и] найти все натуральные числа C++

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

Или воспользуйтесь поиском по форуму:
LosAngeles
Заблокирован
07.10.2011, 13:58     Найти все простые числа на отрезке [a,b]. #11
silent_1991, под "всё" я подразумевал "всё что можно". Тут же ещё рекурсивный вызов как бы, но зато никаких проверок на простоту на этапе выполнения нет. Вплане быстодействия наверно лучше комбинация run\compile time
Код
for (i)
  if (isPrime<i>::value)
    cout << i;
но простота на этапе выполнения проверяется, слишком тривиально, чтобы выкладывать это)

Добавлено через 18 минут
впринципе это всё оптимизации поддаётся, в идеальном случае компилятор может и не вызывать конструкторов и забацать cout подряд один за другим, MVSC2010 почти так и сделал 17-23 он вывел в одном конструкторе
асм
Assembler
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
template <int x, bool y = isPrime<x>::Yes > struct OutputAllPrimes;
 
 
template <int x> struct OutputAllPrimes<x, true>
{
    OutputAllPrimes() 
010910E0  push        ebp  
010910E1  mov         ebp,esp  
    {
        cout << x << " is prime!" << endl;
010910E3  mov         eax,dword ptr [__imp_std::endl (1092044h)]  
010910E8  mov         ecx,dword ptr [__imp_std::cout (1092050h)]  
010910EE  push        eax  
010910EF  push        17h  
010910F1  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (1092058h)]  
010910F7  push        eax  
010910F8  call        std::operator<<<std::char_traits<char> > (1091280h)  
010910FD  add         esp,4  
01091100  mov         ecx,eax  
01091102  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (109205Ch)]  
        OutputAllPrimes<x-1>();
01091108  mov         ecx,dword ptr [__imp_std::endl (1092044h)]  
0109110E  push        ecx  
0109110F  mov         ecx,dword ptr [__imp_std::cout (1092050h)]  
01091115  push        13h  
01091117  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (1092058h)]  
0109111D  push        eax  
0109111E  call        std::operator<<<std::char_traits<char> > (1091280h)  
01091123  add         esp,4  
01091126  mov         ecx,eax  
01091128  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (109205Ch)]  
0109112E  mov         edx,dword ptr [__imp_std::endl (1092044h)]  
01091134  mov         ecx,dword ptr [__imp_std::cout (1092050h)]  
0109113A  push        edx  
0109113B  push        11h  
0109113D  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (1092058h)]  
01091143  push        eax  
01091144  call        std::operator<<<std::char_traits<char> > (1091280h)  
01091149  add         esp,4  
0109114C  mov         ecx,eax  
0109114E  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (109205Ch)]  
01091154  lea         eax,[ebp+0Bh]  
01091157  push        eax  
01091158  call        OutputAllPrimes<13,1>::OutputAllPrimes<13,1> (1091170h)  
    };

7-13 во втором, 5-2 в третьем. Три вызова не слишком много, потенциально может обогнать цикл из mov+test
Yandex
Объявления
07.10.2011, 13:58     Найти все простые числа на отрезке [a,b].
Ответ Создать тему
Опции темы

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