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

а чем суть то задачи? Посчитать и вывести 2 миллиарда * 4 байта = 8 гигабайт мусора на диск? Это и не должно быть быстро.

Или посчитать минимальное число цветов?

Уж наверное надо найти минимальную раскраску, иначе в чём сложность?

[lazychaser]

struct MarkedItem
        {
            public uint index; //простое число
            public uint iter; //итерация, на которой было найдено простое число
        };

        static void Calculate(uint N)
        {
            byte[] colors = new byte[N + 1];
            List<MarkedItem> marked = new List<MarkedItem>();

            colors[1] = 1;
            for (int i = 2; i <= N; i++)
                colors[i] = 2;

            uint p = 2;
            byte maxColors = 2;
            //это цикл для вычеркивания чисел, которые делятся на все найденные простые числа
            for (int i = 2; i * 2 <= N; i++)
            {
                //поиск непомеченных в промежутке от p до i
                for (; p <= i; p++)
                    if (colors[p] == 2) marked.Add(new MarkedItem { index = p, iter = (uint)i - 2 });

                //обновляем все найденные
                for (int j = 0; j < marked.Count; j++)
                {
                    uint mult = (uint)(i - marked[j].iter);
                    uint index = mult * marked[j].index;

                    if (index > N) continue;

                    //берем цвет множителя + 1
                    colors[index] = (byte)(colors[mult] + 1);

                    if (colors[index] > maxColors) maxColors = colors[index];
                }
            }

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

            for (int i = 1; i <= maxColors; i++)
            {
                wr.WriteLine("Color #" + i.ToString());

                for (int j = 0; j < colors.Length; j++)
                    if (colors[j] == i)
                        wr.Write(j.ToString() + " ");

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

            wr.Close();
        }

        static void Main(string[] args)
        {
            Calculate(200000);
        }

Вот что я смог сделать. Работает намного хуже предыдущего алгоритма! Может быть я что-то делаю не так?

[lazychaser]

Уж наверное надо найти минимальную раскраску, иначе в чём сложность?

ну да, я думал это подразумевалось

Уж наверное надо найти минимальную раскраску, иначе в чём сложность?

да ясень пень что надо

вопрос в другом - интересует цифра "минимальное количество цветов" или стопицот мегабайт хлама?

[lazychaser]

Уж наверное надо найти минимальную раскраску, иначе в чём сложность?

да ясень пень что надо

вопрос в другом - интересует цифра "минимальное количество цветов" или стопицот мегабайт хлама?

И то, и то Да я сам в шоке. Предмет называется "Высокоуровневое программирование".

максимальное число делителей - у степеней двойки, так что просто
находишь ближайшие степень двойки <= N

[code]

                  if (colors[p] == 2) marked.Add(new MarkedItem { index = p, iter = (uint)i - 2 });

неудивительно что жутко тормозит. нельзя пользоваться аллокатором во внутреннем цикле!!!!!! которой стопицот мильонов раз будет выполняться!!!!!!!

Вот что я имел ввиду

user@magrathea:~/tmp$ cat p.cc
#include <cstdio>
#include <cstdlib>
#include <cstring>

typedef unsigned long long ui64;

int main(int argc, char **argv)
{
    ui64 N = atoi(argv[1]);

    char *table = new char[N+1];
    memset(table, 0, N+1);

    for (ui64 p = 2; p <= N; p++) {
        if (table[p] == 0) {
            for (ui64 pp = p; pp <= N; pp *= p) {  // цикл по степеням p
                for (ui64 q = pp; q <= N; q += pp) {
                    ++table[q];
                }
            }
        }
    }

    //....

    return 0;
}
user@magrathea:~/tmp$ g++ -o p p.cc -O3 -Wall -W 
p.cc:7: warning: unused parameter 'argc'
user@magrathea:~/tmp$ time ./p 1000000

real	0m0.013s
user	0m0.006s
sys	0m0.007s
user@magrathea:~/tmp$ time ./p 10000000

real	0m0.156s
user	0m0.164s
sys	0m0.012s
user@magrathea:~/tmp$ time ./p 100000000

real	0m2.828s
user	0m2.767s
sys	0m0.048s
user@magrathea:~/tmp$ time ./p 1000000000

real	0m34.574s
user	0m33.804s
sys	0m0.609s
user@magrathea:~/tmp$ time ./p 2000000000

real	1m17.109s
user	1m15.548s
sys	0m1.256s

это без вывода хлама на диск, но мысль думаю ясна

[lazychaser]

мощно, спасибо ) у меня вообще нет опыта решения таких задач