Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 02 июн 2019, 11:21 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Окончательный вид кода, учитывая не нужность в этом случае функции, получился такой:

▼ код
program prime
implicit none
integer :: a(100), x, i, j, temp
logical :: l

i=1; x=3; a(1) = 2

do while (i < 100)

l = .true.
temp = x**0.5

do j = 1,temp
if (mod (x, a(j)) == 0) then
l = .false.
exit
end if
end do

if (l) then
a(i+1) = x
i=i+1
end if

x=x+2
end do


print 100, a
100 format (10i5)
end program prime


То же самое на Аде:

▼ код
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;

procedure prime is
--объявляем массив
type Massiv is array (1..100) of Integer;
a : Massiv;

--объявляем логический тип
type Boolean is (False, True);
l: Boolean;

--объявляем переменные
i, x, temp : Integer;

--процедура печати
procedure Show_Mas(vect: in Massiv) is
begin
for i in vect'First..vect'Last loop
Put(Item => vect(i), Width => 5);
end loop;
end Show_Mas;

--функция вычисления "верхнего края" цикла
function Limit (x : in integer) return integer is
res : Integer;
sq : float;
begin
sq:=float(x); --преобразование в вещественное
sq:=sqrt(sq); --кв. корень
res := Integer (Float'Floor (sq)); --отброс дробной части с переводом в целое'
return res;
end Limit;

-- поехали
begin

i:=1; x:= 3; a(1):= 2;

while i < 100 loop
l:= True;
temp := Limit(x); --обращение к функции

for j in 1..temp loop
if x rem a(j) = 0 then
l := False;
exit;
end if;
end loop;

if l = True then
a(i+1):= x;
i:=i+1;
end if;

x:=x+2;
end loop;

Put("Результат работы:");
New_Line;
Show_Mas(a); --обращение к процедуре печати

end prime;


Весьма интересный и строгий язык. Только из интереса (хотя это в данном случае лишнее) написал с использованием процедуры и функции, поэтому получилось длинно. К сожалению без заданного переноса строки при выводе, пока не знаю как это сделать, печатается на всю ширину консоли с автопереносом, но с заданным числом пробелов между числами. Если кто значет подскажите как сделать перенос строки при печати массива, например после 10-ти первых чисел.

Вот так попроще, без лишних процедур

▼ код
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;

procedure Main is
--объявляем массив
type Massiv is array (1..100) of Integer;
a : Massiv;

--объявляем логический тип
type Boolean is (False, True);
l: Boolean;

--объявляем переменные
i, x, temp : Integer;
sq : float;

-- поехали
begin

i:=1; x:= 3; a(1):= 2;

while i < 100 loop
l:= True;
sq:=float(x);
sq:=sqrt(sq);
temp := Integer (Float'Floor (sq)); --отброс дробной части с переводом в целое'

for j in 1..temp loop
if x rem a(j) = 0 then
l := False;
exit;
end if;
end loop;

if l = True then
a(i+1):= x;
i:=i+1;
end if;

x:=x+2;
end loop;

Put("Результат работы:");
New_Line;
for i in 1..100 loop
Put(Item => a(i), Width => 5);
end loop;

end Main;

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 02 июн 2019, 12:51 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 апр 2016, 13:40
Сообщений: 3550
Cпасибо сказано: 5
Спасибо получено:
624 раз в 591 сообщениях
Очков репутации: 98

Добавить очки репутацииУменьшить очки репутации
С++
#include <cstdlib> 
#include <iostream>
#include <string>
using std::cout;
using std::cin;
using std::endl;

int main()
{ int a[100];
int n,i,j,k;
setlocale(0, "");
a[0]=1; a[1]=2;a[2]=3;n=3;i=2;
while (i<100)
{
n++;
k=0;
for(j=2;j<n;j++)
{
if((n % j)==0) k++;
}
if(k==0) {i++; a[i]=n;}
}
for(j=0;j<100;j++)
cout<<j<<" "<<a[j]<<endl;

system("pause");
}

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 02 июн 2019, 18:25 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
slava_psk, ничего не имею против, но в Ваш код заложен очень медленный алгоритм, очень медленный. Для 100 элементного массива это не критично, но уже на 10000 это жутко медленно. Если есть желание, попробуйте вложить тот же алгоритм, который я вложил на Фортране и Аде (и о котором написал atlakatl).

ps При тестировании, дабы это не тормозило, я убрал блок кода печати:
for(j=0;j<100;j++)
cout<<j<<" "<<a[j]<<endl;

вывел только печать одного 10000 элемента массива для контроля правильности расчета.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 02 июн 2019, 18:44 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 апр 2016, 13:40
Сообщений: 3550
Cпасибо сказано: 5
Спасибо получено:
624 раз в 591 сообщениях
Очков репутации: 98

Добавить очки репутацииУменьшить очки репутации
Emphatic18, а зачем вообще нужен массив из 1000 простых чисел? Какое это имеет прикладное значение? Кроме конечно, как обучение студентов циклам.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 02 июн 2019, 22:10 
Не в сети
Beautiful Mind
Зарегистрирован:
17 апр 2019, 04:57
Сообщений: 1208
Откуда: Грузия
Cпасибо сказано: 99
Спасибо получено:
41 раз в 41 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
запускаешь прогрессии -1+6к и 1+6к перемножаешь числа этих прогрессии на друг друга они пробегают
эти же прогрессии все числа которые не будут задеты их произведением и будут простые числа .
или трудно такую программку создать

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 03 июн 2019, 05:00 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
ammo77
Не путайте народ. Все простые числа имеют разложение [math](6n \pm 1)[/math], но не все числа этого вида простые. Можно проверять на простоту числа только этого вида, будет небольшой выигрыш в расчётах в сравнении с проверкой всех нечётных.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 03 июн 2019, 10:24 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
slava_psk писал(а):
Emphatic18, а зачем вообще нужен массив из 1000 простых чисел? Какое это имеет прикладное значение? Кроме конечно, как обучение студентов циклам.

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

atlakatl писал(а):
Все простые числа имеют разложение (6n±1)
но не все числа этого вида простые. Можно проверять на простоту числа только этого вида, будет небольшой выигрыш в расчётах в сравнении с проверкой всех нечётных.
В этом случае возможны пропуски? Например выпадет какое-то число из перечня?



ps. Обратил внимание на алгоритмы решета Эратосфена (упоминали на прошлой странице) и решета Аткина, при желании можно попробовать, тем более на первый взгляд там возможны параллельные операции.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 03 июн 2019, 19:04 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Алгоритм решета Эратосфена оказался весьма интересным. Суть ниже, никаких делений с остатком и все основные операции параллельны.

program eratosfen
implicit none
integer :: a(2:100), i

!Заполним массив нат. числами 1...100
forall (i=2:100) a(i) = i

!Потрясем решето 4 раза
forall (i=2:50) a(2*i) = 0
forall (i=3:33) a(3*i) = 0
forall (i=5:20) a(5*i) = 0
forall (i=7:14) a(7*i) = 0

!Выжмем нули
a (2:26) = pack (a, a/=0)

!Посмотрим что в остатке
print 100, a(2:26)

100 format (10i5)
end program eratosfen

Результат
Код:
    2    3    5    7   11   13   17   19   23   29
   31   37   41   43   47   53   59   61   67   71
   73   79   83   89   97


До выжимки, сразу после того как 4 раза потрясли решето, в массиве было следующее, для наглядности:

Код:
    2    3    0    5    0    7    0    0    0   11
    0   13    0    0    0   17    0   19    0    0
    0   23    0    0    0    0    0   29    0   31
    0    0    0    0    0   37    0    0    0   41
    0   43    0    0    0   47    0    0    0    0
    0   53    0    0    0    0    0   59    0   61
    0    0    0    0    0   67    0    0    0   71
    0   73    0    0    0    0    0   79    0    0
    0   83    0    0    0    0    0   89    0    0
    0    0    0    0    0   97    0    0    0

Отжать можно в отдельный массив, но что бы не плодить их выжал в первые 25 ячеек существующего массива.

Теперь задача автоматизировать процесс, вставляя в forall нужные числа и не в ручную определять размер выжимки.

program eratosfen
implicit none
integer :: a(2:100), i, j, n

forall (i=2:100) a(i) = i

n = 2
do while (n**2 < 100)

forall (j = n : 100/n) a(n*j) = 0
n = n + 1

do while (a(n)==0)
n = n + 1
end do
end do

j=1
do concurrent (i=2:100)
if (a(i)/=0) j=j+1
end do

a(2:j) = pack (a, a/=0)

print 100, a(2:j)

100 format (10i5)
end program eratosfen


Двумя разными алгоритмами я сформировал массив из 1 миллиона простых чисел. Для контроля правильности расчета были выведены первые 100 простых чисел, а так же последний, миллионный элемент, все сошлось один к одному.

А теперь самое интересное - тестирование на скорость, ради чего и вычислялся миллионный массив (при этом машина у меня древненькая). Первый алгоритм, тот который был приведен в первом сообщении на 2-й странице, справился с задачей за 35,1 секунды, код с реализацией решета Эратосфена сделал все то же самое за 1,09 секунд, не ошибка, в 32,2 раза быстрее! При этом интересным кажется то, что с ростом величины массива разница в "разах" скорее всего будет только расти.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 03 июн 2019, 19:41 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
Emphatic18 писал(а):
В этом случае возможны пропуски? Например выпадет какое-то число из перечня?

Выпадут числа 2 и 3. Отсутствие других доказываем:
1. При делении простого числа на 6 невозможны остатки 0, 2, 4. - иначе число чётное.
2. Невозможен остаток 3 - иначе делимость на 3.
3. Остальные простые дают остатки 1 или 5.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Массив простых чисел
СообщениеДобавлено: 03 июн 2019, 20:22 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
28 апр 2016, 13:40
Сообщений: 3550
Cпасибо сказано: 5
Спасибо получено:
624 раз в 591 сообщениях
Очков репутации: 98

Добавить очки репутацииУменьшить очки репутации
Как же вам эти числа не надоели...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3  След.  Страница 2 из 3 [ Сообщений: 22 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Множество простых чисел и пар простых чисел-близнецов бескон

в форуме Размышления по поводу и без

korolchukvasily

2

257

28 июн 2023, 11:23

Дан массив целых чисел. Найти максимальное число. Сделать в

в форуме Информатика и Компьютерные науки

Nesquik60

0

641

29 июн 2014, 14:02

Сумма простых чисел

в форуме Интересные задачи участников форума MHP

MurChik

15

222

28 янв 2024, 10:52

Группы простых чисел

в форуме Теория чисел

vorvalm

5

1063

03 дек 2014, 15:00

Формула простых чисел?

в форуме Теория чисел

Ferma

18

1087

05 дек 2018, 21:11

Формула для простых чисел

в форуме Размышления по поводу и без

Tirpa

30

1343

22 авг 2019, 23:30

Тройки простых чисел

в форуме Теория чисел

Claudia

5

591

18 июн 2018, 13:13

Свойства простых чисел

в форуме Палата №6

Galina Alexandrovna

13

1569

21 июл 2016, 07:14

Формула для простых чисел

в форуме Размышления по поводу и без

ammo77

1

241

31 янв 2020, 12:22

Последовательность простых чисел

в форуме Теория чисел

DeD

2

654

28 мар 2017, 01:43


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved