:help:

[Comrade_V]

êòîíèáóäü íàïèøèòå â java ïðîãó êîòîðàÿ âûøèòûâàåò íîìåðà êîòîðûå äåëÿòñÿ òîëüêî íà ñåáÿ è åäèíèöó. íó ÷òî òî âðîäå åòîgo

Код: Выделить всё

1
2
3
5
7
11
13
........................ etc äî 10000

[x]

[off]Автоперевод с транслита:[/off]
инет полон, поищи http://google.com/search?q=prime.java

[Белый С.]

[off]x, вот обленились все как, человек учится, а вы ему - иди воруй [/off]

Comrade_V, ну подумай сам - по умолчанию каждое число простое,
но надо прокрутить в цикле все числа от 2 до числа-1 (достаточно до квадравного корня из числа) и проверить остаток от деления. Если 0 -> уже не простое. Если осталось простым - выводи.

По ссылке xа выходит много фигни, в частности http://www.cs.princeton.edu/introcs/23f ... .java.html.
Критика:
1)тебе надо вокруг цикла из этой программы гонять цикл по N от 1 до 10000.
Параметр N доставать из коммандной строки уже не нужно.
2)Максимальное значение для i (корень из N) лучше вычислить заранее, вне цикла по i.
3)Можно заменить ==0 на отрицание (!). Выражение равно нулю когда оно ложно.
4)Вместо вывода простое ли число, выводишь его ЕСЛИ оно простое.

[Comrade_V]

Áåëûé Ñ.,
ñïàñèáà.. âîò ìîé ðåçóëüòàò

Код: Выделить всё

public class blah {

    public static void main(String[] args)  {

     for(int i = 3; i < 100; i+=2)
{
	int count = 0;
	
	for(int x = 3; x <=i; x+= 2)
	{
		if(i%x==0)
		{
		    count++;
}
}
	if(count==1)
{
	System.out.println(i);
}
}
}
}

[off]added Wed Mar 17, 2004 05:50:[/off]

à âîîáøå ïîñåòèòå ìîþ ñòðàíèöó ðîãðàìèðîâàíèÿ http://friendz.amillo.net/viewforum.php?f=10 òàì òàê ñêàçàòü âåñ ïðîöåññ ìîåãî îáó÷åíèÿ

[Белый С.]

Comrade_V, похоже на правду, но ты не учёл ряд вещей:
1)твоё задание вроде было от одного, а не от трёх
2)вроде было до 10000 а не до 100
3)я ж тебе сказал, что достаточно проверять не до i, a до квадратного корня из i, и счётчик должен остаться нулём, это СИЛЬНО сократит количество операций.
4)ты исключил чётные числа - минимум ускорил в два раза, НО используя выход из цикла по нахождению делителя позволит БЫСТРО отбросить много вариантов.

[off]добавлено Ср Мар 17, 2004 13:03:[/off]

Comrade_V, попробуй так:

Код: Выделить всё

public class Primes
{public static void main(String[] args)
 {for(int i=1;i<10000;i+=2) 
  {int p,m=Math.sqrt(i);
   for(int x=3;x<=m;x+=2) 
    if(!(p=i%x)) break;
   if(p) System.out.println(i); 
  } 
 } 
}

Я написанное тебе не тестировал, отладка на тебе, тем не менее заметь пару изюминок: классы обычно называют с большой буквы, в отличии от полей и методов (переменных и функций); корень вычисляется однажды для каждого числа (и для любого i<10000 будет менее 50 проверок); если что-то разделилось, то дальше не проверяется (количество делителей никого не волнует); в p=i%x один знак равенства - так надо, это не сравнение, а присвоение.

[Comrade_V]

Áåëûé Ñ.,
ÿ íå ñîâñåì ïîíÿë ÷òî òû ñ êîðíåì äåëàåø, +

Код: Выделить всё

int p,m=Math.sqrt(i); 

âûäàåò

possible loss of precision

<<(ýòî ÿ ïðî ñåáÿ);

[Белый С.]

Comrade_V, подумай: минимальный нетривиальный (не 1 и не само число) делитель числа не превосходит корня из этого числа. А корень можно заранее вычислить, чтобы не вычислять каждый раз, так как это более дорогостоящая операция. Про потерю точности: можно округлить вниз, вычислив Math.floor(Math.sqrt(i)).

[x]

[off]Автоперевод с транслита:[/off]

Белый С. твой код работать не будет, ибо там ты перепутал типы переменных, да и вообще весь синтаxис ошибочный. Там отлаживать нечего, его переписать надо, ну и вот я переписал, ради интереса (придерживаясь идеи с корнем). Хотелось узнать будет ли работать быстрее метод с корнем. Вот результат (добавил кусок кода для выведения времени работы проги):

Код: Выделить всё

public class Primes {
public static void main(String[] args) {

long t1 = System.currentTimeMillis();
  int m = 10000;
        for (int i=2; i<m; ++i) {
            if (isprime(i)) {
                System.out.println(i);
            }
        }
long t2=System.currentTimeMillis();
long t=t2-t1;
System.out.println("vremya = " + t);

    }

     public static boolean isprime(int chislo){
        long m = Math.round(Math.sqrt(chislo)) + 1;
        for (int i=2; i<m; ++i) {
            if (chislo%i == 0) {
                return false;
            }
        }
        return true;
    }

}

[off]Автоперевод с транслита:[/off]

в результате, время варьировала от 250 до 350 мс.

измерил и для прежднего кода, который запостил Комраде_В, получилось от 650 до 750 мс. Эксперимент удался, корень рулит

[Белый С.]

x, любопытные наблюдения. Единственное несоответствие типов данных - это корень, но его достаточно округлить. Хочешь сказать что надо long вместо int? Не помню, ибо 6 лет не прикасался к Java. И какой синтаксис _весь_ ошибочный?

Специфика: ты не выводишь число 1 (в задании требовалось, мелочь, я придирчивый).
Неучтённые тобой оптимизации:
1)корень достаточно округлить вниз (а не в ближайшую сторону), но это мелочь.
2)Не надо "+1" и "<", когда можно "<=", тоже мелочь.
3)Делимое и делитель достаточно гонять по нечётным числам => сужается перебор. Делимое и так отсеклось бы на двойке, а вот делитель - двойная работа. Comrade_V прав.
4)Около 10000 вызовов функции менее чем за секунду - недёшево (call и ret, параметры, локальные переменные), куда лучше сделать вложенный цикл и break вместо return.

И при этом корень всё равно рулит Учтя пожелания, думаю снизишь время ещё существеннее. А вообще я ожидал большей разницы => где-то ты зарыл собаку. Возможно из-за того, что чисто на вывод чисел уходит львиная часть времени. Для справки, сколько времени ушло бы (на твоём компе) на примитив вроде этого (2500 можно заменить на количество простых чисел)

Код: Выделить всё

public class LowerBound
{public static void main(String[] args)
 {long t1=System.currentTimeMillis(); 
  int m=1000,n=2500;
  for(int i=0;i<n;++i)
   System.out.println(m); 
  long t2=System.currentTimeMillis(); 
  long t=t2-t1;
  System.out.println("vremya = " + t); 
 }
}

Предвосхищаю вывод: разница во времени должна быть более драматичной если бы задача ставилась вывести количество простых чисел. [off]Спасибо за интересную дискуссию.[/off]

[x]

насчет синтаксиса

Код: Выделить всё

{int p,m=Math.sqrt(i);

- даже если округлять, тип переменной должен быть double, а не интегер, и еще самое главное что p не инициализируется

Код: Выделить всё

if(!(p=i%x)) break;

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

Код: Выделить всё

if(p)

возвратит чтонибудь только если p будет boolean (как isprime, в моем случае). это заодно и ответ почему return а не break .

ну а теперь паяснения
для вывода 1, достаточно менять i = 2, на i =1
1. а без разницы
2. в принципе правильно
3. ага. теоретически так и должно быть, но я сам не знаю почему тесты не показали никакой разницы..
4. не думаю что будет быстрее, но нету желания проверять.

примитив выдал 125 мс Но учитывай что я утром был на амд 1.7 гхз, а ща я дома на п 2.53 гхз. Сами классы(о которых речь) выдают соответсвенно ~370 и ~90

[Bandit]

Помогите замутить курсовик по моделированию систем.Тема:Анализ и макромоделирование интегральных микросхем.Нужно построить модели и сделать прогу.И сколько это будет стоить? Пожалуйста помогите.Мой номер 79512126 Саша