| Автор | Задача на С++ |
|---|
Кто может помочь с задачей,условие:
Найти все простые числа в промежутке от а до в.
Вот мое решение,но оно с функцией, как его заменить на операцию с "for". Я пробовал ,но что-то не вышло.
#include <iostream.h>
bool Simple (int a)
{
bool flag=true;
for (int i=2; i<a; i++)
{
if (!(a%i))
{
flag=false;
}
}
return flag;
}
int main()
{
int a,b;
cout << “vvedit’ chislo a(a<b):”;
cin >>a;
cout << “vvedit’ chislo b(b>a):”;
cin >>b;
cout << “vse prosti chisla:” endl;
for (int i=a+1; i<b; i++)
{
if (!(a%i))
{
cout <<i << “ “;
}
}
}
Сори что криво,задачу перебирал на ворде((( |
По-моему она.
#include <iostream>
using namespace std;
int main(){
int c,n;
cin >> n; cout << endl;
for (c=1;c<=n;c++){
bool m=true;
int a=c;
do{
int b=a%10;
if (b==0){ m=false; break;}
if(c%b!=0) m=false;
a=a/10;
}while (a>0);
if (m) cout << c << endl;
}
system("pause");
return 0;} |
| Хотя нет, сори, невнимательно прочитал условие. |
| Это вообще другая задача. |
Мммм, а подробней?
Тебе нужно простое решение через for, чтобы найти все простые в промежутке от а до b, так?
Тогда примерно так.//У меня в голове сейчас каша из синтаксиса и компилятора нет сишного, поэтому на псевдо-коде.
cin>>a;//ввод а минимальное значение//
cin>>b;/ввод б максимальное значение//
for (j=a;j<=b;j++)//Цикл по j от минимального до максимального значения//
{
z=0;//Обнуление счетчика
for (i=2;i<j;i++)//цикл перебора делителя от 2 до проверяемого числа//
{
if (j%i==0){z++;}
// Если так случилось, что число поделилось без остатка на число в промежутке от 2 до а-1, то делаем счетчик + 1//
}
if (z==0) {cout<<j<<endl;}
//Если так случилось, что ни один делите не поделил без остатка и мы ни разу не прибавили наш счетчик z, то можно выводить число j на экран со словами "простое число" //
}
Примерно понятно? |
Вроде пашет.
#include <iostream>
using namespace std;
int main(){
int a,b;
cout << " a = "; cin >> a; cout << endl;
cout << " b = "; cin >> b; cout << endl;
for (int i=a+1; i<b; i++)
{
bool flag = true;
for (int j=2; j < i; j++)
{
if ( i % j == 0) flag = false;
}
if (flag) cout << i << endl;
}
system ("pause");
} |
Ну и отлично)
п.с.Хорошая замена счетчика на флаг - в тему) |
if (j%i==0){z++;}
// Если так случилось, что число поделилось без остатка на число в промежутке от 2 до а-1, то делаем счетчик + 1//
В задаче Найти все простые числа в промежутке от а до в, а не посчитать... Поэтому найденные простые числа надо в массив (коллекцию) складывать.
И проверку на простоту немного изменить - не обязательно при проверке 1001 проверять все цикл перебора делителя от 2 до проверяемого числа.
Во первых, до целой части его половины. Если мы проверили 500 и число 1001 всё ещё простое, то нет смысла проверять 501 - т.к. 501*2 > 1001, а значит 501 никак не может быть делителем 1001.
Во вторых, нужно делить не на все подряд числа, а только на простые. Тем более, они уже хранятся в массиве (коллекции). |
for (i=2;i<j;i++)//цикл перебора делителя от 2 до проверяемого числа//
Во первых, до целой части его половины. Если мы проверили 500 и число 1001 всё ещё простое, то нет смысла проверять 501 - т.к. 501*2 > 1001, а значит 501 никак не может быть делителем 1001.
Возмите корень квадратный проверяемого числа и до него проверяйте - быстрее программа работать будет |
Возмите корень квадратный проверяемого числа
Тоже верно, что-то я затупил. |
| Решето Эратосфена лучше попробуйте. |
Решето Эратосфена
Не годится. Решето используют для поиска протых чисел до n. Для поиска в промежутке этот алгоритм не годится. |
для FireSwarm:
Не годится. Решето используют для поиска протых чисел до n.
Решето все равно нужно, ибо ищутся сначала простые (от 1 до n = sqrt(b)), на которые может делиться проверяемые числа. А далее проверяем саму делимость уже имея короткий набор делителей. Отдельно можно оптимизировать, когда области 1..n и a..b пересекаются. |
Отдельно можно оптимизировать, когда области 1..n и a..b пересекаются.
Вернее тогда нужно решето 1..b и вывести только числа из диапазона a..b:) |
Я бы не стал так делать в любом случае.
Если брать академическую задачу - это необоснованное увеличение сложности алгоритма.
Если брать реальную. Например, в криптографии я использовал простое число - (500! + 1). Ай да проверять его своим решетом... |
Массив и коллекции это все хорошо, да и оптимизация это прекрасно, но тут задача на уровне школы.
Человек попросил простой способ через for, как записать в массив и сам поймет это не относиться к программе, да и условия хранения не оговорили в задании.
Зачем так сложно давать людям программы? Решето к примеру - прекрасный способ, но по моему это задача для первого курса универа или школьного курса - лучше помогать, как можно проще, имхо.
Пускай покрутится лишняя 500-сотка чисел - компу до фени ведь, он не калькулятор)//Надеюсь//
п.с.Ну а так верно, в криптографии за такую реализацию не похвалят :D |
Пускай покрутится лишняя 500-сотка чисел - компу до фени ведь, он не калькулятор)//Надеюсь//
Так-то он так. Но будущих прогеров с детства нужно приучать не писать лабуду. Конечно, оптимизировать код нужно начинать ровно тогда, когда возникает такая необходимость и ни секундой раньше. Но даже в школе есть смысл давать задачи по оптимизации алгоритмов, хотя бы как дополнительные. Тем более в данном случае это способен сделать даже 5-тиклассник. |
| Да,спасибо всем большое))) Сколько же программистов розвелось)) |
для FireSwarm:
В данном случае была решена задача через функцию, но она не удовлетворила, т.к. функций мы еще (типо) не изучали, а через for я чёт напортачил и ответ чисел у меня не выводило. |
