Недавно я участвовал в небольшом конкурсе Java-программирования в моей школе. Мой партнер и я только что закончили наш первый чистый класс oop, и большинство вопросов были вне нашей лиги, поэтому мы остановились на этом (и я немного перефразирую): обратная сторона также проста, например, если n = 18, ваша программа должна вывести 31 ", потому что 31 и 13 являются простыми. В вашем файле .class будет передан контрольный пример всех возможных чисел от 1 до 2 000 000 000, и он должен будет вернуть правильный ответ в течение 10 секунд, чтобы его считали действительным.
Мы нашли решение, но для более крупных тестовых случаев это заняло бы больше 10 секунд. Я вполне уверен, что есть способ сдвинуть диапазон циклов с n, .. 2 000 000 000, так как вероятная капля необходимости зацикливаться так далеко, когда n - небольшое число, мала, но в любом случае мы прервали цикл, когда число прост при обоих условиях найден. Сначала мы выполняли цикл от 2, .. n независимо от того, насколько велик он был, потом я вспомнил правило о циклическом переходе только к квадратному корню из n. Любые предложения о том, как сделать мою программу более эффективной? У меня не было классов, занимающихся анализом сложности алгоритмов. Вот наша попытка.
public class P3
{
public static void main(String[] args){
long loop = 2000000000;
long n = Integer.parseInt(args[0]);
for(long i = n; i<loop; i++)
{
String s = i +"";
String r = "";
for(int j = s.length()-1; j>=0; j--)
r = r + s.charAt(j);
if(prime(i) && prime(Long.parseLong(r)))
{
System.out.println(i);
break;
}
}
System.out.println("#");
}
public static boolean prime(long p){
for(int i = 2; i<(int)Math.sqrt(p); i++)
{
if(p%i==0)
return false;
}
return true;
}
}
ps извините, если я сделал неправильное форматирование кода, это мой первый пост здесь. Кроме того, в выходных данных должен был стоять знак «#» после каждой строки, о чем говорит строка после цикла Спасибо за любую помощь, которую вы, ребята, предлагаете !!!