Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Простые числа простыми средствами  [new]
AR®
Member

Откуда: Подмосковье
Сообщений: 337
Решил в выходные показать детям, что такое в арифметике простые числа, и что с ними можно сделать. И вот как я их получил:
declare	@max2test	int	= 1000000	-- максимальное проверяемое при данном запуске число
declare	@num2test	int	= (select case when max(p) is null then 2 when max(p)=2 then 3 else max(p)+2 end from primes31)	-- начальное проверяемое число; если в таблице ничего нет, то 2, если максимальное 2, то 3, иначе первое нечётное за максимальным уже найденым при предыдущих запусках

set nocount on		-- без этого на больших @max2test ssms.exe съест память сообщениями "(1 row(s) affected)"
while @num2test <= @max2test
begin
	if not exists (	select	1				-- если в таблице нет 
			from	primes31			-- для очередного проверяемого числа 
			where	p <= ceiling(sqrt(@num2test))	-- не превосходящих корня квадратного из него (обязательно использовать ceiling() и "<=", а не "<")
			and	@num2test % p = 0		-- делителей без остатка
			)
		insert primes31(p) values(@num2test)		-- то оно - простое
		
	if @num2test = 2147483647	-- если достигнуто максимальное возможное для int (которое, к слову, тоже простое)
		break			-- завершить
	else				-- иначе 
		set	@num2test = case when @num2test = 2 then 3 else @num2test + 2 end	-- берём следующее нечётное
end
set nocount off


Конечно, решение на C/C# работало бы в разы быстрее, но зато здесь всё наглядно и всё сразу оказывается в базе данных.
17 апр 17, 10:51    [20406893]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
AR®
Member

Откуда: Подмосковье
Сообщений: 337
Для полноты картины создание таблицы
create table primes31(p int primary key)
17 апр 17, 10:54    [20406907]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
waszkiewicz
Member

Откуда:
Сообщений: 1090
циклы-то зачем?
17 апр 17, 11:48    [20407111]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
AR®
Member

Откуда: Подмосковье
Сообщений: 337
waszkiewicz
циклы-то зачем?

А как?
17 апр 17, 12:28    [20407249]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
waszkiewicz
Member

Откуда:
Сообщений: 1090
select value from integers i1
where not exists (
select 1 from integers i2
where
i2.value<i1.value
and i1.value%i2.value = 0
and i2.value>1


хотя бы так
17 апр 17, 12:40    [20407281]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
waszkiewicz
Member

Откуда:
Сообщений: 1090
waszkiewicz,
для полноты картины таблицу целых чисел создай сам
17 апр 17, 12:40    [20407284]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
AR®
Member

Откуда: Подмосковье
Сообщений: 337
Можно и так, но
1)заполнение integers всё равно будет в цикле
2)в предельном случае даже для int она будет не маленькая (свыше миллиарда записей)
3)а её произведение даже на часть самой себя кратковременно будет ещё больше и временно сделает сервер маложивым.
17 апр 17, 12:53    [20407339]     Ответить | Цитировать Сообщить модератору
 Re: Простые числа простыми средствами  [new]
AR®
Member

Откуда: Подмосковье
Сообщений: 337
Потестил способ без цикла. Уже на ~100 млн. ничего хорошего не получилось.
19 апр 17, 17:28    [20415911]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить