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

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

06.09.2009, 20:06. Просмотров 8179. Ответов 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] или как там на си правильно массивы описывать?
http://www.cyberforum.ru/cpp-beginners/thread1857096.html
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2009, 20:06
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Вывод всех простых чисел. (C++):

Удаление всех простых чисел из массива
Помогите, пожалуйста, решить задачу в с++. Как удалить все простые числа из...

Найти позиции всех простых чисел!
С клавиатуры вводится 20 простых чисел, найти позиции всех простых чисел! #...

Возврат всех простых чисел из массива
Помогите пожалуйста решить. Желательно с пояснениями и комментариями Дан...

Печать всех простых чисел до 500
Печать всех простых чисел до 500 Помогите, плз))

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

15
ISergey
Maniac
Эксперт С++
1407 / 918 / 148
Регистрация: 02.01.2009
Сообщений: 2,744
Записей в блоге: 1
06.09.2009, 20:13 #2
Цитата Сообщение от Gr1f0n Посмотреть сообщение
Вывести все простые числа от 1 до n
http://www.cyberforum.ru/visual-cpp/thread30569.html

Цитата Сообщение от Gr1f0n Посмотреть сообщение
И массив хочется описать как A:array[1..N] или лучше A:array[1..N+N^2] или как там на си правильно массивы описывать?
C++
1
2
const int n = 100;
int arr[n]; //[0..99]
1
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]
если вместо задания константой поставить ввод от пользователя то прога компилиться и выдает ошибку..
0
Gravity
569 / 563 / 64
Регистрация: 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;
}
1
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
07.09.2009, 08:52 #5
2Gravity: проверять нужно до sqrt(n), а не до n/2
0
Yurii_74
paladin
283 / 183 / 7
Регистрация: 25.02.2009
Сообщений: 592
07.09.2009, 12:08 #6
Можно улучшить все это проверяя число на делимость только на найденные уже простые числа. При поиске большего количества простых чисел должно работать быстрее.
0
mamedovvms
2918 / 839 / 324
Регистрация: 30.04.2009
Сообщений: 2,633
07.09.2009, 12:22 #7
шаг нужно сделать равным 2
0
Yurii_74
paladin
283 / 183 / 7
Регистрация: 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 ...
0
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 не выдает надо менять тип данных на какой подскажите, а то на парах толком ничего не рассказывают.
0
zim22
depict1
276 / 141 / 4
Регистрация: 11.07.2009
Сообщений: 606
07.09.2009, 17:02 #10
Цитата Сообщение от Gr1f0n Посмотреть сообщение
надо менять тип данных на какой подскажите
__int64
0
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 не надо менять?...
з.ы. все равно вылетает... не выводит...
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
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()
0
Gr1f0n
1 / 1 / 0
Регистрация: 05.09.2009
Сообщений: 10
07.09.2009, 17:22  [ТС] #13
odip во первых это си++ а мне надо просто си пока что но все равно пригодиться как плюсы буде изучать...
Т.е. в твоей выводятся простые числа с 1 до 100? или в общем первые 100 простых чисел?
з.ы. первые 100 и у меня выводятся проблемы начинаются с 1 до 1000 уже не выводит... там их 168
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
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
Потому что по массиву быстрее во много раз.
И чем дальше - тем быстрее.
0
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 штук разницы и выходит
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
07.09.2009, 18:08 #16
все народ не паникуйте...таблица на 2 страницы по 9 столбцов на страницу на первой странице 43строчки на столбец а на второй 44 а я не впалил и посчитал как 43 вот 9 штук разницы и выходит
)))))))
0
07.09.2009, 18:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2009, 18:08
Привет! Вот еще темы с решениями:

Вывод простых чисел от m до n
Здравствуйте! Возникла проблемка с задачкой. Требуется вывести все простые...

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

Найти количество всех простых чисел на отрезке
Решите пожалуйста, завтра необходимо сдать. Задание: Разработка...

Поиск всех простых чисел в заданном диапазоне
Необходимо разработать программу ,вычисляющую все простые числа в произвольном...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

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