Решето Эратосфена, без использования массива

@MrDreher · Регистрация: 02.10.2012

Студворк — интернет-сервис помощи студентам

Для решения задачи не использовать массивы. Это работа на дополнительный бал... Реализвал так как понял, препод сказал что не тем методом решил - нужно по другому.... Просьба если возможно написать код с пояснениями(с комментариями), чтоб я понял как программа работает а не просто скопировал...
Вот код который я написал:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace rescheto_rot
{
    class Program
    {
        static void Main(string[] args)
        {
            int g=0;
            Console.WriteLine("Vvedite K(nachalo diapazona):");
            int k = int.Parse(Console.ReadLine()); //Получаем начало диапазона
            Console.WriteLine("Vvedite N(konez diapazona):");
            int n = int.Parse(Console.ReadLine()); //Получаем конец диапазона
            int a = 1;
            Console.WriteLine("\nRescheto Erotosfena:\n");
            for (int i = 1; i <=n;i++)
            {
                a++;
                for (int z = 2; z<=n; z++)
                {
                    if (a == z) {  }
                    else if (a % z != 0) {}
                        //123 :)
                    else if (a%z==0) { g++; }
                }
                if (a > k)
                {
                    if (g == 0) { Console.Write("{0} ", a); }
                }
                g = 0;
            }
            Console.ReadLine();
        }
    }
}

Добавлено через 27 минут
В Google набираю «Решето Эратосфена на C#», находит кучу сайтов – на которых скопирован один и тот же код с использованием массивов…
15-20 раз уже перечитал страничку на Вики, все равно не могу понять: как без использования массива можно заранее вычеркнуть из диапазона значения кратные 2,3и т.п.? Если не использовать массивы, то придется использовать «наружный» цикл, который будет проверять – подходит ли число, если оно подходит – выводить его на экран…. Затем операция повторяется (N-ное количество раз) и этой же переменной присваивается другое значение. Как реализовать 2 пункт метода Эратосфена в таких условиях? Оно должно уже на втором пункте вычеркнут некоторые значения…. В голове бардак… (

Добавлено через 39 минут
Очень нужно это реализовать, неужели никто не поможет?

Psilon · 02.10.2012, 23:21

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

C#
1
2
3
4
5
6
7
private static bool IsPrime(int x)
        {
            if (x < 1) return false;
            for (int i = 2; i * i <= x; i++)
                if ((x % i) == 0) return false;
            return true;
        }

То есть программа выглядела бы

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
 
namespace rescheto_rot
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Vvedite K(nachalo diapazona):");
            int k = int.Parse(Console.ReadLine()); //Получаем начало диапазона
            Console.WriteLine("Vvedite N(konez diapazona):");
            int n = int.Parse(Console.ReadLine()); //Получаем конец диапазона
            Console.WriteLine("\nRescheto Erotosfena:\n");
            for (int i = k; i <=n;i++)            
                if (IsPrime(i))
                   Console.Write(i + " ");            
            Console.ReadLine();
        }
 
 
        private static bool IsPrime(int x)
        {
            if (x < 1) return false;
            for (int i = 2; i * i <= x; i++)
                if ((x % i) == 0) return false;
            return true;
        }
    }
}

И оно бы работало, только никакого решета тут нет. А без массива его не построить. Ну если построить, расскажите нам, пусть вам препод скажет, потому что меня всегда интересовали чудеса, особенно в этой области

@MrDreher · 03.10.2012, 01:03 **[ТС]**

Сообщение от Psilon

И оно бы работало, только никакого решета тут нет. А без массива его не построить. Ну если построить, расскажите нам, пусть вам препод скажет, потому что меня всегда интересовали чудеса, особенно в этой области

Спасибо. Попробую так сдать, надеюсь зачтет.

@turbanoff · 03.10.2012, 09:19

Сообщение от Psilon

А без массива его не построить. Ну если построить, расскажите нам, пусть вам препод скажет, потому что меня всегда интересовали чудеса, особенно в этой области

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

@Vaso · 03.10.2012, 10:08

Формально не массив - это все, что не массив.

Можно извратиться, как угодно:
1) хранить числа через запятую в строке, и удалять их оттуда;
2) хранить числа в списке, очереди, словаре (Dictonary<int, int> - не массив, адназначна!);
3) хранить в таблице SQL;
4) хранить числа в потоке (файле, или в памяти, и т.п.)

Но суть останется той же, база данных есть база данных.

Препод просто любопытствует, кто как извратится, ну и пытается вас поглубже покопать возможности языков программирования самостоятельно.

Напишите все перечисленные варианты, слабо? Ради одного балла

Добавлено через 1 минуту
кстати, на чистом SQL решение достаточно красиво смотрелось бы )) ща набросаю

Добавлено через 9 минут

Не по теме:

заверните эту хрень в C#, и сдавайте ))

SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DECLARE @halt tinyint
    , @CURRENT INT
 
SET @halt = 0
 
SELECT top 1000 
    ROW_NUMBER() OVER(ORDER BY id) x 
INTO #Eratosfen
FROM sys.sysobjects 
CROSS JOIN (SELECT top 100 1 x FROM sys.messages) x
 
DELETE FROM #Eratosfen WHERE x = 1
 
CREATE TABLE #Result (y INT NOT NULL)
 
while (@halt = 0)
BEGIN
    SELECT @CURRENT = MIN(x) FROM #Eratosfen
    INSERT #Result (y) VALUES(@CURRENT)
    DELETE FROM #Eratosfen WHERE (x % @CURRENT) = 0
    IF NOT EXISTS(SELECT * FROM #Eratosfen)
        SET @halt  = 1
END
 
SELECT y FROM #Result

Psilon · 03.10.2012, 11:56

turbanoff, я там понял, что без массива имеется ввиду без "Любой структуры данных, содержащей множество элементов"

@Vaso · 03.10.2012, 13:46

Сообщение от Psilon

turbanoff, я там понял, что без массива имеется ввиду без "Любой структуры данных, содержащей множество элементов"

Любая программа выполняется в оперативной памяти, а это тоже в каком-то далеком приближении массив

Psilon · 03.10.2012, 13:53

Vaso, ну вы поняли, о чем я говорю

В данном случае на организацию памяти закрывают глаза, имеется ввиду, чтобы конкретная программа не использовала массив. Потому как у меня был знакомый с говнокодом на паскале, там на 200 строк было 50 переменных. Щас кстати покажу:
Вычисления в Panel, создание формулы

@MrDreher · 03.10.2012, 14:24 **[ТС]**

Сообщение от Psilon

turbanoff, я там понял, что без массива имеется ввиду без "Любой структуры данных, содержащей множество элементов"

Так и есть.
Всем спасибо за ответы, ответ зачтен. Принял то что было во 2 посте.

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	03.10.2012, 11:56
	turbanoff, я там понял, что без массива имеется ввиду без "Любой структуры данных, содержащей множество элементов" 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	03.10.2012, 13:53
	Vaso, ну вы поняли, о чем я говорю В данном случае на организацию памяти закрывают глаза, имеется ввиду, чтобы конкретная программа не использовала массив. Потому как у меня был знакомый с говнокодом на паскале, там на 200 строк было 50 переменных. Щас кстати покажу: Вычисления в Panel, создание формулы 0

Решето Эратосфена, без использования массива

Решение