Интересная Задачка!

[Виктория Боско]

Здравствуйте, недавно мне задана была интересная задача: не используя никаких программ в Windows, а только саму оболочку Windows, ---необходимо написать программу, которая
считает сумму первых 10 000 000 простых чисел.
Скажите, пожалуйста, вообще возможно это? Какой должен быть язык? И Какое решение данной программы?

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

[GoodDA]

Сервер сценариев WSH. Языки сценариев VBScript и JScript
http://www.intuit.ru/department/os/compromtwin/4/

+

Примеры программ для поиска простых чисел на Java


public class EasyNumber {
private static boolean easy;

public static void main(String[] args) {
System.out.println(2);

for (int i = 3; i < 10000000; ++i) {
easy = true;

for (int j = 2; j < i / 2 + 1; ++j) {
if (i % j == 0) {
easy = false;
break;
}
}

if (easy)
System.out.println(i); - а тут надо суммировать!

}
}
}

[Виктория Боско]

Извините пожалуйста, наверное глупый вопрос:

данный текст программы - это вся программа? и ее только необходимо всавить в файл с расширением .js и далее в командной строке написать csckript и далее место нахожение файла?
просто с таким языком я не знакома и не могу правильно понять что и где в данной программе находится,

при компиляции данного кода в cmd выдается сообщение Ошибка компиляции Microsoft Jscript: предполагается наличие ";"

Что делать и как быть?....пожалуйта не злитесь, объясните

[Виктория Боско]

Это что такая сложная задача?

Пожалуйста, кто-нибудь ответьте на мое предыдущее сообщение

[Serge_Bliznykov]

Виктория,
1) сохраните нижеуказанный код в файлик с расширением .VBS (например, simple_sum.vbs)
и запустите его в проводнике (просто даблклик на имени файла)...

Function isSimple(iNumber)
  isSimple = True
  K = int(iNumber / 2)
  for j = 2 to K+1
    if (iNumber mod j) = 0 then
        isSimple = False
    End if    
  next  
End Function


S = 1  rem  1 - простое число

for i = 3 to 1000 step 1
  if isSimple(i) Then 
     rem msgbox "Простое число: " & i
     S = S + i
  End if   
next

msgbox "Сумма простых чисел в диапазоне от 1 до 1000 " & vbCrLf & " равна S = " & S

Это просто как примерчик...
По поводу решения Вашей задачи смотри ниже...

2) Ваша задача какая-то безумная... Вы хотя бы представляете, сколько времени займёт поиск простых чисел в диапазоне от 1 до 10 миллионов?!?!?
А, если я правильно понял условие задачи, надо искать не среди чисел от 1 до 10 000 000 - а нужно найти ПЕРВЫЕ 10 миллионов простых чисел! Это будет ЕЩЁ ГОРАЗДО ДОЛЬШЕ...
Короче, кому нужны такие "Интересные Задачки" — я не понимаю. Препода — в топку...

Удачи!

[Виктория Боско]

я с вами полностью согласна!
огромное спасибо за помощь!

еще есть небольшой вопросик : что означает int в строчке K = int(iNumber / 2)?

еще почитала в интернте - единица она не является простым числом, т.к имет лишь 1 положительный делитель, хотя и удовлетворяет критерию простых чисел, тогда S = 2 так надо исправить, ведь 2 является простым числом, хотя оно и четное?

[Serge_Bliznykov]

Виктория, приношу Вам свои глубочайшие извинения. Рад, что Вы заметили мою оплошность. Безусловно, Вы правы - единица НЕ ЯВЛЯЕТСЯ простым число, зато двойка - является...

Последовательность простых чисел начинается с
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

Пора мне в среднюю школу восстанавливать забытое ;-)

что означает int в строчке K = int(iNumber / 2)?

проверять делители нужно только до числа, равно ЦЕЛОЧИСЛЕННОМУ делению исходного числа на 2
int(x) возращает целую часть от X
таким образом, например, при iNumber = 5
int(5 / 2) будет равно 2 (т.е. для 5 мы будем проверять, делится ли это число на 2 и на 3 (K+1)...

[alexBlack]

Оказывается (для меня это было откровением) сумму первых 10 млн. простых чисел можно вычислить на домашнем компьютере. Даже первый миллиард чисел просеивается достаточно быстро (< 10 мин).

Сумма первых 10000000 простых чисел = 870530414842019

Ниже код. Это не совсем подходит под условия задачи, поскольку сделано в VS, но, думаю, и в vbs будет работать если убрать Console.Writeln.

Module Module1

    Sub Main()

        Dim M = 100000, j
        Dim N = 200000000, a(200000000) As Byte
        a(1) = 0
        a(2) = 2
        a(3) = 3
        a(4) = 0
        a(5) = 5
        a(6) = 0
        a(7) = 7
        a(8) = 0
        a(9) = 0
        a(10) = 0
        a(11) = 11
        For i = 12 To N Step 1
            If (i Mod 2 = 0) Or (i Mod 3 = 0) Or (i Mod 5 = 0) Or (i Mod 7 = 0) Or (i Mod 11 = 0) Then
                a(i) = 0
            Else
                a(i) = 1
            End If
            If i Mod (M * 10) = 0 Then
                Console.WriteLine("Заполнение массива " + (i / (M * 10)).ToString() + " / " + (N / (M * 10)).ToString())
            End If
        Next

        Dim S As Decimal REM double
        Dim k = 5
        S = 2 + 3 + 5 + 7 + 11

        REM Здесь будет пауза 
        REM Трудно вычеркнуть первые несколько тысяч чисел
        REM дальше процесс идет быстрее
        For i = 13 To N Step 1
            If a(i) > 0 Then
                S = S + i
                k = k + 1

                If k = 10000000 Then REM А это наши 10 000 000 
                    Console.WriteLine("Сумма первых " + k.ToString() + " простых чисел = " + S.ToString())
                    REM Похоже Basic не поддерживает break
                End If

                If i >= 13 Then
                    REM Console.WriteLine(i)
                    j = i + i
                    While j <= N
                        a(j) = 0
                        j = j + i
                    End While
                End If
            End If
            If i Mod M = 0 Then
                Console.WriteLine("Просеивание " + (i / M).ToString() + " / " + (N / M).ToString())
            End If
        Next
        Console.WriteLine("Сумма первых " + k.ToString() + " простых чисел = " + S.ToString())
        REM MsgBox("Сумма первых " & k & " простых чисел = " & S)
        REM Сумма первых 10000000 простых чисел = 870530414842019
        REM Сумма первых 5761455 простых чисел = 279209790387276            // массив   100 000 000
        REM Сумма первых 11078937 простых чисел = 1075207199997334          // массив   200 000 000
        REM Сумма первых 26355867 простых чисел = 6404774487532576          // массив   500 000 000
        REM Сумма первых 50847534 простых чисел = 24739512092254535         // массив 1 000 000 000

    End Sub

End Module

[Виктория Боско]

я пробывала по методу Serge_Bliznykov подсчитать до 1 000 000, ждала час, так и недождалась


а ваш метод alexBlack не работает

[alexBlack]

Сообщение от Виктория Боско

я пробывала по методу Serge_Bliznykov подсчитать до 1 000 000, ждала час, так и недождалась

а ваш метод alexBlack не работает

Не то чтобы не работает. Просто разница в синтаксисе.
Попробуйте этот вариант. Теперь можно записать в vbs-файл и выполнить.

        Dim m
        M = 1000
        dim j
        Dim n
        N = 200000
        dim a(200000)
        a(1) = 0
        a(2) = 2
        a(3) = 3
        a(4) = 0
        a(5) = 5
        a(6) = 0
        a(7) = 7
        a(8) = 0
        a(9) = 0
        a(10) = 0
        a(11) = 11
        For i = 12 To N Step 1
            If (i Mod 2 = 0) Or (i Mod 3 = 0) Or (i Mod 5 = 0) Or (i Mod 7 = 0) Or (i Mod 11 = 0) Then
                a(i) = 0
            Else
                a(i) = 1
            End If
        Next

        Dim S 
        s = 0 
        Dim k
        k = 5
        S = 2 + 3 + 5 + 7 + 11

        For i = 13 To N Step 1
            If a(i) > 0 Then
                S = S + i
                k = k + 1

                If k = 10000000 Then 
                    MsgBox("Сумма первых " & k & " простых чисел = " & S)
                End If

                If i >= 13 Then
                    REM 
                    j = i + i
                    While j <= N
                        a(j) = 0
                        j = j + i
                    WEnd 
                End If
            End If
        Next
        MsgBox("Сумма первых " & k & " простых чисел = " & S)

обратите внимание - размер массива я уменьшил чтобы долго не ждать, т.к. никаких сообщений во время расчета не выдается. Кроме того нужно учитывать, что это скрипт. Выделение таких массивов может и не пройти.