Раскраска чисел

[lazychaser]

Такая задача: даны числа от 1 до N. Если одно число делится на другое, то у них должен быть разный цвет.

Стоит ограничение по времени.

Меня смущает то, что N может быть 2 млрд! Я сейчас выясняю, насколько это верно.

Сейчас делаю так: сначала ищу все простые числа, затем все составные перебирая все комбинации произведений простых чисел (основная теорема арифметики). Числа сохраняются по цветам в отдельные файлы, а потом компилируются в один.

Программа работает для N = 5 000 000 5 сек (большее время занимает нахождение простых чисел)

Откуда задача?

По моему решается очень просто - посчитай для каждого числа число его простых делителей. Это и будет номер цвета.

[lazychaser]

ну проблема в том, что это не так-то просто для большого числа, и когда их много.

Я чутка поработал над алгоритмом, хотя и скорость не дюже выросла.
Сейчас я сначала генерирую простые числа в интервале от 1 до . Также есть массив чисел от 1 до , в котором хранятся цвета уже найденных чисел (индекс соответствует числу). Алгоритм простой: если число делится на два, то берем цвет из таблицы цветов под индексом и прибавляем к нему единицу, иначе начинаем перебирать простые числа в качестве делителей. Если доходим до конца списка, то значит текущее число тоже простое, иначе цвет опять же берем из таблицы с индексом .

Работает 6с для 10 млн, получается 75мб файл с самой раскраской, цветов 24.

Работает около 4 минут для 100 млн и получается 850мб файл и 27 цветов.

Вот сам код (.net):

        List<StreamWriter> writers = new List<StreamWriter>();

        List<uint> primeNumbers = new List<uint>();
        ushort[] numberColors;

        uint N;

        void AddNum(uint num, ushort color)
        {
            if (writers.Count < color)
                writers.Add(new StreamWriter(String.Format("Color{0}", color)));

            writers[(int)color - 1].Write(num);
            writers[(int)color - 1].Write(" ");

            if (num < numberColors.Length) numberColors[(int)num] = color;
        }

        int MergeAndClear()
        {
            foreach (StreamWriter w in writers)
                w.Close();

            StreamWriter wr = new StreamWriter("result.txt");

            int colors = writers.Count;

            char[] buf = new char[255];
            for (int i = 1; i <= writers.Count; i++)
            {
                string fileName = String.Format("Color{0}", i);
                StreamReader r = new StreamReader(fileName);

                wr.WriteLine("Color #" + i.ToString());
                int cnt;
                do
                {
                    cnt = r.Read(buf, 0, 255);
                    if (cnt > 0) wr.Write(buf, 0, cnt);
                } 
                while (cnt > 0);
                r.Close();

                File.Delete(fileName);

                wr.WriteLine();
                wr.WriteLine();
            }
            wr.Close();

            writers.Clear();

            return colors;
        }

        bool primeInt(uint n)
        {
            if (n < 2) return false;

            if (n == 2) return true;

            if (n % 2 == 0) return false;

            for (int i = 1; i < primeNumbers.Count; i += 1)
                if (n % primeNumbers[i] == 0) return false;

            return true;
        }

        ushort GetLevel(uint num)
        {
            if (num == 1) return 1;

            if ((num & 1) == 0)
                return (ushort)(numberColors[(int)(num >> 1)] + 1);

            int prime = 0;
            while ((prime < primeNumbers.Count) && (num % primeNumbers[prime] != 0)) prime++;

            if (prime == primeNumbers.Count) return 2;

            return (ushort)(numberColors[(int)(num / primeNumbers[prime])] + 1);
        }

        private void button1_Click(object sender, EventArgs e)
        {
            N = 0;

            try
            {
                N = uint.Parse(textBox1.Text);
            }
            catch (Exception)
            {
                MessageBox.Show("Введите число.");
            }

            DateTime dt = DateTime.Now;

            numberColors = new ushort[(N >> 1) + 1];

            uint to = (uint)Math.Sqrt((double)N);
            for (uint i = 3; i <= to; i++)
                if (primeInt(i)) primeNumbers.Add(i);

            double primeTime = (DateTime.Now - dt).TotalMilliseconds;
            dt = DateTime.Now;

            for (uint i = 1; i <= N; i++)
                AddNum(i, GetLevel(i));

            double procTime = (DateTime.Now - dt).TotalMilliseconds;
            dt = DateTime.Now;

            int colors = MergeAndClear();

            double mergeTime = (DateTime.Now - dt).TotalMilliseconds;

            MessageBox.Show(String.Format("Готово!\nВремени на нахождение простых чисел: {0} мс"+
                "\nВремя на нахождение составных чисел: {1} мс"+
                "\nВремя на выполнение задачи: {2} мс"+
                "\nОбщее время: {3} мс"+
                "\nПолучилось цветов: {4}", primeTime, procTime, mergeTime, primeTime + procTime + mergeTime, colors));
        }

Есть идеи по оптимизации?

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

И вы не ответили на вопрос откуда задача. Пока не ответите, больше не буду помогать. (вдруг с идущего контеста - были уже преценденты)

Есть идеи по оптимизации?

да, на C или на чем угодно рассчитать все 2 гигабайта данных, потом просто командой dd копируешь первые N байт из своего файла. быстрее некуда.

[lazychaser]

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

И вы не ответили на вопрос откуда задача. Пока не ответите, больше не буду помогать. (вдруг с идущего контеста - были уже преценденты)

Сейчас посмотрю (почему-то у меня такая мысль была, но я на нее не обратил внимания).
А задача не конкурсная, это нам почему-то задали для получения автомата по C# %)

да, на C или на чем угодно рассчитать все 2 гигабайта данных, потом просто командой dd копируешь первые N байт из своего файла. быстрее некуда.

умно ничего не скажешь :-D

[lazychaser]

Ха, я что-то подобное уже делал, но не догадался про вычеркивание )) Сейчас замутим.

[lazychaser]

Удалось реализовать через решето, но не особо быстро, нужна подсказка

Удалось реализовать через решето, но не особо быстро, нужна подсказка

C++