Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.07.2018, 11:27   #1
Tulio
Новичок
Джуниор
 
Регистрация: 25.07.2018
Сообщений: 6
По умолчанию Быстрый код поиска чисел не делящихся.

Привет!
У меня такая проблема: мне надо сделать программ который для двоих числ ("a" и "b") сказать сколько между ними числ (с ними тоже) которые не делится на никакого числа из данного множества. Как это сделать быстрее?

Я сделал такой вот код:

Код:
#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
int main() {
 
	set<int> multiset;
	int n, temp, q, a, b, how_many, x;
	bool divided;
	cin >> n;
	while(n--) {
		cin >> temp;
		multiset.insert(temp);
	}
 
	cin >> q;
	while(q--) {
		cin >> a >> b;
		how_many = 0;
		for (int i = a; i <= b; i++) {
			divided = false;
			for (int x : multiset) {
				if (i % x == 0) {
					divided = true;
					break;
				}
			}
			if(!divided) how_many++;
		}
		cout << how_many << '\n';
	}
	return 0;
}
но он очень медленный (тест: https://ideone.com/a7Tzmq)

Извини за мой русский - я не росиянин.
Tulio вне форума Ответить с цитированием
Старый 25.07.2018, 11:52   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

я бы не использовал multiset
просто в цикле проверял делимость.

но у меня вопрос.
ведь a и b не подходят по условию (не подходят, потому что а делится на a, а число b делится на b), поэтому их не считаем, так ?
какой ответ, например, для диапазона
3 7 ?
ответ 2 ? (это числа 4, 5) ?

такой вариант не устроит?
Код:
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
	
	int a, b, how_many, i,j;
	bool divided;

	cin >> a >> b;
	if(a>b){
		i=a; a=b; b=i;
	}
	how_many = 0;
	for (int i = a+1; i < b; i++) {
			
			divided = false;
			for (j=a; j<=(i/2);j++) {
				if (i % j == 0) {
					divided = true;
					break;
				}
			}
			if(!divided) how_many++;
	}
	cout << how_many << '\n';
	return 0;
}
https://ideone.com/dOdv1A

Последний раз редактировалось Serge_Bliznykov; 25.07.2018 в 11:58.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 25.07.2018, 12:18   #3
Tulio
Новичок
Джуниор
 
Регистрация: 25.07.2018
Сообщений: 6
По умолчанию

Нет, нет, ты мне не понял. Мне надо сказать сколько в промежутком [a,b], которые не делятся та никакого число с донного множества (данный он есть во время активности программа).

Примеры:
1:
set = {1}
range = [3, 7]
out = 0 (нет числ которые не деляются на 1)

2:
set = {2,3}
range = [3,7]
out = 2 (толькл 5 и 7 не делаются на 2 и 3)

3:
set = {5, 11, 8}
range = [1,100]
out = 63 (63 числ в [1,100] которые не делятся на 5, 11 и 8)

4:
set = {4, 3, 5, 7}
range = [1,100]
out = 34

принятие: все числа в set и range будут натуральные

Последний раз редактировалось Tulio; 25.07.2018 в 12:21.
Tulio вне форума Ответить с цитированием
Старый 25.07.2018, 12:21   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

В multiset-е же заданный список делителей, его не отбросишь )

А что под ускорить имеется в виду? Получилось ~0.5 сек для чисел по ссылке делфийской прогой, а сколько нужно?

add

для начала можно проверить четность делимого и делителя, и не проверять остаток от деления, если делимое не четное, а делитель четный например
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 25.07.2018 в 12:29.
Аватар вне форума Ответить с цитированием
Старый 25.07.2018, 12:27   #5
Tulio
Новичок
Джуниор
 
Регистрация: 25.07.2018
Сообщений: 6
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
В multiset-е же заданный список делителей, его не отбросишь )
Да. Где возможно искать ускорения знаю: multiset данный раз, а range-ов может быть бесконечное количество и поэтому я бы хотел сделать то так что если кто-то искает похоже range это будет быстрее, например:

range = [1, 1000]
а потом:
range = [3,500]
думаю что другого можно бы не вычислять. Но не знаю как.

или:
range = [1,1000]
а потом:
range = [700,1100]

должен быть способ чтобы 700-1000 не делать второй раз.
Tulio вне форума Ответить с цитированием
Старый 25.07.2018, 12:35   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Есть же максимальный диапазон range. Если он не очень большой, то можно массив держать, соответствующей размерности, в котором отмечать проверялось ли число и, если проверялось, то есть ли для него делитель в списке делителей.

add

Попробовал, в 5 раз быстрей стало для того набора чисел
Четность не проверял, возможно еще чуть-чуть можно ускорить
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 25.07.2018 в 12:44.
Аватар вне форума Ответить с цитированием
Старый 25.07.2018, 12:44   #7
Tulio
Новичок
Джуниор
 
Регистрация: 25.07.2018
Сообщений: 6
По умолчанию

Как это хорошо сделать? Максимальный range (сейчас, но если будет больший то не очень) это [1,10^6].
Tulio вне форума Ответить с цитированием
Старый 25.07.2018, 12:54   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Массив байтов соответствующего размера. Индекс соответствует числу из диапазона. Массив инициализировать нулем. Если 0 - проверка и заполнение 1 или 2, если 1 - нет делителей, 2 - есть
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 25.07.2018, 13:12   #9
Tulio
Новичок
Джуниор
 
Регистрация: 25.07.2018
Сообщений: 6
По умолчанию

Да. Теперь код:

Код:
#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
int main() {
 
	set<int> multiset;
	int numbers[1000000] = {0};
	int n, temp, q, a, b, how_many, x;
	bool divided;
	cin >> n;
	while(n--) {
		cin >> temp;
		multiset.insert(temp);
	}
	cin >> q;
	while(q--) {
		cin >> a >> b;
		how_many = 0;
		for (int i = a; i <= b; ++i) {
			if (numbers[i] == 2) continue;
			if (numbers[i] == 1) how_many++;
			else {
				divided = false;
				for (int x : multiset) {
					if (i % x == 0) {
						divided = true;
						break;
					}
				}
				if (divided) {
					numbers[i] = 2;
				} else {
					numbers[i] = 1;
					how_many++;
				}
			}
		}
		cout << how_many << '\n';
	}
 
	return 0;
}
ходит быстрее 2 раза! Спасибо!
Ещё подумал что можно сделать сортировку числ из multiset потому что это больше правдоподобие, что 2 будет делить данное число тем например 125. Хорошо думаю? Пожалуй только можно ещё сделать.
Tulio вне форума Ответить с цитированием
Старый 25.07.2018, 13:25   #10
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

numbers[i] == 2 можно и не проверять, достаточно сравнить с 1 и 0
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сумма всех трехзначных чисел, не делящихся ни на 5, ни на 7 на Prolog abc7 Помощь студентам 2 27.12.2016 13:49
Найти количество трёхзначных чисел делящихся на 7 и не делящихся на 3 TsykunovDmitriy Паскаль, Turbo Pascal, PascalABC.NET 3 07.05.2014 23:05
код поиска чисел Фибоначчи sam5213 Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 0 20.03.2012 23:17
Количество чисел, делящихся на 11 CrazyRabbit Помощь студентам 9 09.08.2009 01:56
Вывод чисел, делящихся на каждую из своих цифр. Паскаль ЯншинаВера Помощь студентам 3 08.04.2008 11:50