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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 48, средняя оценка - 4.60
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
#1

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

06.09.2009, 20:06. Просмотров 6547. Ответов 15
Метки нет (Все метки)

Задали задачку.
Вывести все простые числа от 1 до n
Примерно сделал на паскале. До 100 все работает а дальше он не может ворочать такими цифрами.
Pascal
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
Var
A:array[1..9999] of longint;
z,x,i,n: longint;
begin
writeln('N='); Readln(n);
i:=1;
A[i]:=i;
Repeat           {Цикл заполнения массива т.е. все числа будут под своим номером в массиве}
i:=succ(i);
A[i]:=i;
until i=n;
z:=2;             {Первые 2 числа произведение которых дат сложное число}
x:=2;
Repeat
If x<10 then begin       {Обнуляем сложные числа}
i:=z*x;
x:=succ(x);
A[i]:=0;
end
else begin
z:=succ(z);
x:=2;
i:=z*x;
A[i]:=0; end;
until z>n;
i:=2;
Repeat           {Выводим все числа массива отличные от нуля}
if A[i]=0 then
i:=succ(i)
Else begin
writeln(A[i],',');
i:=succ(i); end;
until I>=n;
end.
вот что-то такое мне нужно делать но на си. И массив хочется описать как A:array[1..N] или лучше A:array[1..N+N^2] или как там на си правильно массивы описывать?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ISergey
Maniac
Эксперт С++
1346 / 879 / 51
Регистрация: 02.01.2009
Сообщений: 2,643
Записей в блоге: 1
06.09.2009, 20:13     Вывод всех простых чисел. #2
Цитата Сообщение от Gr1f0n Посмотреть сообщение
Вывести все простые числа от 1 до n
Вывод все простых чисел из заданного диапазона

Цитата Сообщение от Gr1f0n Посмотреть сообщение
И массив хочется описать как A:array[1..N] или лучше A:array[1..N+N^2] или как там на си правильно массивы описывать?
C++
1
2
const int n = 100;
int arr[n]; //[0..99]
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
06.09.2009, 20:39  [ТС]     Вывод всех простых чисел. #3
Данный вывод простого числа на плюсах... на просто си у меня чего то не работает...

Добавлено через 7 минут
Цитата Сообщение от ISergey Посмотреть сообщение
const int n = 100; int arr[n]; //[0..99]
если вместо задания константой поставить ввод от пользователя то прога компилиться и выдает ошибку..
Gravity
557 / 551 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
06.09.2009, 20:45     Вывод всех простых чисел. #4
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
#include <stdio.h>
 
int simple(int n)
{
    int i;
    
    if(n <= 1)
       return 0;
    for(i = 2; i <= n/2; i++)
       if(n % i == 0)
          return 0;
    return 1;
} 
 
int main(void)
{
    int i, n;
    
    printf("Введите n: ");
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
       if(simple(i))
          printf("%d ", i);
    return 0;
}
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 08:52     Вывод всех простых чисел. #5
2Gravity: проверять нужно до sqrt(n), а не до n/2
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
07.09.2009, 12:08     Вывод всех простых чисел. #6
Можно улучшить все это проверяя число на делимость только на найденные уже простые числа. При поиске большего количества простых чисел должно работать быстрее.
mamedovvms
2915 / 836 / 93
Регистрация: 30.04.2009
Сообщений: 2,615
07.09.2009, 12:22     Вывод всех простых чисел. #7
шаг нужно сделать равным 2
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
07.09.2009, 13:05     Вывод всех простых чисел. #8
Цитата Сообщение от mamedovvms Посмотреть сообщение
шаг нужно сделать равным 2
Можно ли построить последовательность разниц между соседними простыми числами не узнавая их? То есть можно ли продолжить этот ряд: 1, 2, 2, 4, 2, 4, 4, 2, 6, 2 ...

Добавлено через 24 минуты
немного неправильно ряд записал: 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2 ...
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
07.09.2009, 16:51  [ТС]     Вывод всех простых чисел. #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
#include <stdio.h>
 int main(void)
 {
     int i,m,n;
     printf("N=");
     scanf("%d",&n);
     m=n*n;
     int Arr[m];
     for (i=2; i<=n; i++)
     {
         Arr[i]=i;
     };
     int a,b;
       for (a=2; a<=n; a++)
       {
           for (b=2; b<=n; b++)
           {
               i=a*b;
               Arr[i]=0;
               };
               };
     int s=0;
      for (i=2; i<=n; i++)
      {
          if (Arr[i]!=0)
          {
                printf("%d ",Arr[i]);
                s++;
          }
      };
      printf("Summ=%d",s);
      getch();
      return 0;
 }
вот по простому на мой взгляд... но! больше чем до 500 не выдает надо менять тип данных на какой подскажите, а то на парах толком ничего не рассказывают.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
07.09.2009, 17:02     Вывод всех простых чисел. #10
Цитата Сообщение от Gr1f0n Посмотреть сообщение
надо менять тип данных на какой подскажите
__int64
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
07.09.2009, 17:11  [ТС]     Вывод всех простых чисел. #11
Цитата Сообщение от Gravity Посмотреть сообщение
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
#include <stdio.h>
 
int simple(int n)
{
    int i;
    
    if(n <= 1)
       return 0;
    for(i = 2; i <= n/2; i++)
       if(n % i == 0)
          return 0;
    return 1;
} 
 
int main(void)
{
    int i, n;
    
    printf("Введите n: ");
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
       if(simple(i))
          printf("%d ", i);
    return 0;
}
контрольные суммы не совпадают: простых чисел от 1 до 6000 - 774, а здесь из 783 непорядок =)

Добавлено через 3 минуты
Цитата Сообщение от zim22 Посмотреть сообщение
__int64
а в этой строчке
printf("%d ",Arr[i]);
%d не надо менять?...
з.ы. все равно вылетает... не выводит...
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 17:16     Вывод всех простых чисел. #12
Можно ли построить последовательность разниц между соседними простыми числами не узнавая их? То есть можно ли продолжить этот ряд: 1, 2, 2, 4, 2, 4, 4, 2, 6, 2 ...
Нельзя.
Распределение простых чисел не поддается этой закономерности.
Теоремы такие есть.

Добавлено через 2 минуты
Поиск простых чисел через массив.
Записываем ранее найденные простые числа в массив и используем этот массив для проверки.
Вот достаточно быстрый алгоритм нахождения первых 100 простых чисел.
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
#include <iostream>
#include <math.h>
 
using namespace std;
 
const int MAX_S_SIZE= 100;
 
void calc_simple( int size, int *data );
 
 
/**************************************/
int main( void ) {
 
int i;
int sa[MAX_S_SIZE];
 
calc_simple( MAX_S_SIZE, sa );
for ( i= 0; i<MAX_S_SIZE; i++ ) {
        cout <<" " <<sa[i];
}
cout <<endl;
 
return 0;
 
} // main()
 
 
/**************************************/
void calc_simple( int size, int *data ) {
 
int sn, tind, outind, max_div;
bool s_flag;
 
if ( size<1 ) { return; }
 
data[0]= 2;
outind= 1;
sn= 1;
for ( ; outind<size; outind++ ) {
        for ( ; ; ) {
                sn+= 2;
                s_flag= 1;
                max_div= (int)sqrt( sn );
                for ( tind= 1; tind<outind; tind++ ) {
                        if ( data[tind] > max_div ) { break; }
                        if ( sn % data[tind] == 0 ) {
                                s_flag= 0; break;
                        }
                }
                if ( s_flag ) { break; }
        }
        data[outind]= sn;
}
        
} // calc_simple()
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
07.09.2009, 17:22  [ТС]     Вывод всех простых чисел. #13
odip во первых это си++ а мне надо просто си пока что но все равно пригодиться как плюсы буде изучать...
Т.е. в твоей выводятся простые числа с 1 до 100? или в общем первые 100 простых чисел?
з.ы. первые 100 и у меня выводятся проблемы начинаются с 1 до 1000 уже не выводит... там их 168
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 17:37     Вывод всех простых чисел. #14
простых чисел от 1 до 6000
У меня тоже получилось 783 штуки.
Откуда ты взял что их должно быть 774 не понятно

Добавлено через 2 минуты
Там от C++ просто ввод-вывод
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
#include <stdio.h>
#include <math.h>
 
#define MAX_S_SIZE 1000
 
void calc_simple( int size, int *data );
 
 
/**************************************/
int main( void ) {
 
int i;
int sa[MAX_S_SIZE];
 
calc_simple( MAX_S_SIZE, sa );
 
for ( i= 0; i<MAX_S_SIZE; i++ ) {
    printf( " %d", sa[i] );
}
printf( "\n" );
 
return 0;
 
} /* main() */
 
 
/**************************************/
void calc_simple( int size, int *data ) {
 
int sn, tind, outind, max_div;
int s_flag;
 
if ( size<1 ) { return; }
 
data[0]= 2;
outind= 1;
sn= 1;
for ( ; outind<size; outind++ ) {
        for ( ; ; ) {
                sn+= 2;
                s_flag= 1;
                max_div= (int)sqrt( sn );
                for ( tind= 1; tind<outind; tind++ ) {
                        if ( data[tind] > max_div ) { break; }
                        if ( sn % data[tind] == 0 ) {
                                s_flag= 0; break;
                        }
                }
                if ( s_flag ) { break; }
        }
        data[outind]= sn;
}
        
} /* calc_simple() */
Добавлено через 54 секунды
Массив на 100 элементов - выводит первые 100 простых чисел.
В C-ной версии уже 1000 элементов.

Добавлено через 6 минут
з.ы. первые 100 и у меня выводятся проблемы начинаются с 1 до 1000 уже не выводит... там их 168
Потому что по массиву быстрее во много раз.
И чем дальше - тем быстрее.
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
07.09.2009, 18:02  [ТС]     Вывод всех простых чисел. #15
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
#include <stdio.h>
 int main(void)
 {
     int i,n;
     printf("N=");
     scanf("%d",&n);
     int Arr[n];
     for (i=2; i<=n; i++)
     {
         Arr[i]=i;
     };
     int a,b;
       for (a=2; a<=n; a++)
       {
           for (b=2; b<=n; b++)
           {
               i=a*b;
               if (i<n)
               Arr[i]=0;
               };
               };
     int s=0;
      for (i=2; i<=n; i++)
      {
          if (Arr[i]!=0)
          {
                printf("%d ",Arr[i]);
                s++;
          }
      };
      printf("Summ=%d",s);
      getch();
      return 0;
 }
вот конечная прога все написал все получилсь. НО тоже 783. А сравнивал я с таблицей простых чисел от 1 до 6000 там из написано 774.
причемдо 2671 все правильно считает (387), а до 3001 уже на больше чем должно быть (431выдает 430 надо). Но проверил эти 43 последних числа все норм где еще 1 появляеться непонятно =(

Добавлено через 15 минут
все народ не паникуйте...таблица на 2 страницы по 9 столбцов на страницу на первой странице 43строчки на столбец а на второй 44 а я не впалил и посчитал как 43 вот 9 штук разницы и выходит
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2009, 18:08     Вывод всех простых чисел.
Еще ссылки по теме:

C++ Найти сумму всех простых чисел в интервале от 0 до 1000000
Найти произведение всех простых чисел что меньше n C++
C++ Поиск всех простых чисел в заданном диапазоне
C++ Вывод всех простых чисел в диапазоне от 1 до 100
C++ Найти количество всех простых чисел на отрезке

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 18:08     Вывод всех простых чисел. #16
все народ не паникуйте...таблица на 2 страницы по 9 столбцов на страницу на первой странице 43строчки на столбец а на второй 44 а я не впалил и посчитал как 43 вот 9 штук разницы и выходит
)))))))
Yandex
Объявления
07.09.2009, 18:08     Вывод всех простых чисел.
Ответ Создать тему
Опции темы

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