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

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

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

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

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

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

Найти позиции всех простых чисел! - C++
С клавиатуры вводится 20 простых чисел, найти позиции всех простых чисел! # include&lt;iostream&gt; using namespace std; int main() { ...

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

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

Вывод простых чисел от m до n - C++
Здравствуйте! Возникла проблемка с задачкой. Требуется вывести все простые числа от m до n, при условии, что 2&lt;=m&lt;=n&lt;=1000000. Если нет...

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

15
ISergey
Maniac
Эксперт С++
1375 / 886 / 52
Регистрация: 02.01.2009
Сообщений: 2,661
Записей в блоге: 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]
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
562 / 556 / 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;
}
1
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.09.2009, 08:52 #5
2Gravity: проверять нужно до sqrt(n), а не до n/2
0
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
07.09.2009, 12:08 #6
Можно улучшить все это проверяя число на делимость только на найденные уже простые числа. При поиске большего количества простых чисел должно работать быстрее.
0
mamedovvms
2917 / 838 / 93
Регистрация: 30.04.2009
Сообщений: 2,627
07.09.2009, 12:22 #7
шаг нужно сделать равным 2
0
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 ...
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 / 2
Регистрация: 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
Эксперт С++
7157 / 3219 / 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()
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
Эксперт С++
7157 / 3219 / 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
Потому что по массиву быстрее во много раз.
И чем дальше - тем быстрее.
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2009, 18:02
Привет! Вот еще темы с ответами:

Найти количество всех простых чисел на отрезке - C++
Решите пожалуйста, завтра необходимо сдать. Задание: Разработка нерекурсивных функции. Разработать функцию, которая для заданного...

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

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

Напишите программу нахождения всех трехзначных простых чисел - C++
Найти все трехзначные простые числа


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

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

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