как проверить парность введенного числа ?
нужно добавить в код конструкцию для проверки парности вводимого числа.
Т.е. если число парное - выполняется сумирование через цикл, если непарное - вывод в консоль "error"
Т.е. если число парное - выполняется сумирование через цикл, если непарное - вывод в консоль "error"
Код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Threading;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int n = 0;
int sum = 0;
while (n <= 0)
{
Console.WriteLine("Введите количество чисел:");
n = Convert.ToInt32(Console.ReadLine());
}
for (int i = 0; i < n; i++)
{
Console.WriteLine("Введите {0} число:", i + 1);
sum += Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine("Сумма чисел: {0}", sum);
Console.ReadKey(true);
}
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Threading;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int n = 0;
int sum = 0;
while (n <= 0)
{
Console.WriteLine("Введите количество чисел:");
n = Convert.ToInt32(Console.ReadLine());
}
for (int i = 0; i < n; i++)
{
Console.WriteLine("Введите {0} число:", i + 1);
sum += Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine("Сумма чисел: {0}", sum);
Console.ReadKey(true);
}
}
}
Парное число - это четное.
Получается, что в цикле For, перед суммированием нужно проверять введенное число на четность. И, если введенное число четное, то выполнять суммирование. Иначе - писать сообщение в консоль и прерывать цикл.
Ну и завершение программы отработать, чтобы сумма не выводилась, если цикл был прерван.
Получается, что в цикле For, перед суммированием нужно проверять введенное число на четность. И, если введенное число четное, то выполнять суммирование. Иначе - писать сообщение в консоль и прерывать цикл.
Код:
int num; // объявить перед циклом
Console.WriteLine("Введите {0} число:", i + 1);
num = Convert.ToInt32(Console.ReadLine());
if (num % 2 == 0)
sum += num;
else
{
Console.WriteLine("error");
break;
}
Console.WriteLine("Введите {0} число:", i + 1);
num = Convert.ToInt32(Console.ReadLine());
if (num % 2 == 0)
sum += num;
else
{
Console.WriteLine("error");
break;
}
Причем тут четные? Два простых числа парные, если разность их равна двум. Простое число -- целое число большее 1 и которое делится без остатка только на 1 и на себя. Т.е. простые числа: 2, 3, 5, 7 и т.д. Парные из них -- 3 и 5, 5 и 7 и т.д.
Если почитать Wiki, то узнаем, что:
Примеры: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), ... , (599, 601), (617, 619), ...
Соответственно, надо
1) проверять является ли введенное число (например, с) простым;
2) является ли хотя бы одно из чисел (с-2) или (с+2) простым.
Код на Delphi я себе ещё вчера на бросал, а вот C# я никогда не изучал. Поэтому сегодня пришлось поставить VS2012 и почитать книгу для чайников по C#.
Поэтому за код строго не судите, но работает он на все 100 ;).
Конечно алгоритм нахождения простого числа - написан мной без оптимизации и так сказать в лоб. Поэтому вы на просторах инете можете найти более "красивое" решения поиска простых чисел.
Что же касается второго пункта - тоже не очень красиво, т.к. согласно Wiki (а мы все знаем, кто её пишет):
Код можно сильно оптимизировать, проверяя не все числа на простоту, а только те, которые соответствуют приведенному выше правилу. (Но это уже в качестве Вашего домашнего задания остается).
Ну и вот непосредственно программа на C#:
Код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int n = 0;
int sum = 0;
int c = 0;
while (n <= 0)
{
Console.WriteLine("Введите количество чисел:");
n = Convert.ToInt32(Console.ReadLine());
}
for (int i = 0; i < n; i++)
{
Console.WriteLine("Введите {0} число:", i + 1);
c = Convert.ToInt32(Console.ReadLine());
if (IsTwinP(c))
{
sum += c;
}
}
Console.WriteLine("Сумма чисел: {0}", sum);
Console.ReadKey(true);
}
public static bool IsPrime(int c)
{
if (c < 2)
{
return false;
}
else{
for (int i = 2; i <= Math.Truncate(Math.Sqrt(c)) ; i++)
{
if (c % i == 0)
{
return false;
}
}
return true;
}
}
public static bool IsTwinP(int c)
{
if (IsPrime(c))
{
if (IsPrime(c + 2) || IsPrime(c - 2))
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int n = 0;
int sum = 0;
int c = 0;
while (n <= 0)
{
Console.WriteLine("Введите количество чисел:");
n = Convert.ToInt32(Console.ReadLine());
}
for (int i = 0; i < n; i++)
{
Console.WriteLine("Введите {0} число:", i + 1);
c = Convert.ToInt32(Console.ReadLine());
if (IsTwinP(c))
{
sum += c;
}
}
Console.WriteLine("Сумма чисел: {0}", sum);
Console.ReadKey(true);
}
public static bool IsPrime(int c)
{
if (c < 2)
{
return false;
}
else{
for (int i = 2; i <= Math.Truncate(Math.Sqrt(c)) ; i++)
{
if (c % i == 0)
{
return false;
}
}
return true;
}
}
public static bool IsTwinP(int c)
{
if (IsPrime(c))
{
if (IsPrime(c + 2) || IsPrime(c - 2))
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
}
}
PS.
1) Вопрос
1) Вопрос
не совсем корректен. Т.к. я писал про парные простые числа. Но может есть какие-то другие парные числа?... (типа как все четные или в сумме дающие какое-то значение и тд и тп).
2)
- я не писал. Просто забыл. Но я надеюсь, с этим вы сами справитесь (добавить else и вывод слова Ошибка!)
Приведенный код вроде правильный. Но, придется объяснять откуда взялось сравнение с корнем.
Вот решение совсем уж "в лоб", только на основе определения простоты и парности чисел. Без всякой оптимизации и проверок, не ввел ли пользователь букву вместо цифры и т.п. Правда, код на C++.
P.S. Можно использовать для оптимизации алгоритма несколько соображений.
1)простое число -- нечетное число (за исключением числа 2, которое простое). Доказательство очевидно, поскольку все четные кратны двум, а значит уже делимы без остатка хотя бы на двушку.
2)Если число составное, то его можно представить в виде произведения целых a=m*M (1<m<=M); значит корень(a)=корень(m*M), т.е. среднему геометрическому; значит корень(а) лежит между m и M. Поэтому, "забраковать" число как не простое можно выполнив проверки лишь для чисел <= корня от него.
Т.е. первую функцию можно переписать так:
Вот решение совсем уж "в лоб", только на основе определения простоты и парности чисел. Без всякой оптимизации и проверок, не ввел ли пользователь букву вместо цифры и т.п. Правда, код на C++.
Код:
#include <iostream>
using namespace std;
//проверка, простое ли число c
bool prime(int c) {
if (c < 2) return false; //т.к. от 2 и выше могут быть
// проверяем на остаток деления на все меньшие кроме 1
// (при c = 2 этот цикл пропускается)
for (int i = 2; i < c; i++)
if (!(c % i)) return false; //если нет остатка, то не простое
// прошедшее цикл (а также с = 2) - простое
return true;
}
//проверка парности c;
//само c должно быть простым и хотябы одно из отстоящих от
//него на 2 должно быть тоже простым
bool twixed(int c) {
if (prime(c))
if (prime(c - 2) || prime(c + 2))
return true;
return false;
}
int main() {
int n, sum, c;
n = sum = c = 0;
while (n <= 0) {
cout << "Введите количество чисел:";
cin >> n ;
cout << endl;
}
for (int i = 0; i < n; i++) {
cout << "Введите " << i+1 << " число:";
cin >> c ;
if (twixed(c))
sum += c;
else cout << "Ошибка: число не является парным\n";
cout << endl;
}
cout << "Сумма парных чисел: " << sum << endl;
return 0;
}
using namespace std;
//проверка, простое ли число c
bool prime(int c) {
if (c < 2) return false; //т.к. от 2 и выше могут быть
// проверяем на остаток деления на все меньшие кроме 1
// (при c = 2 этот цикл пропускается)
for (int i = 2; i < c; i++)
if (!(c % i)) return false; //если нет остатка, то не простое
// прошедшее цикл (а также с = 2) - простое
return true;
}
//проверка парности c;
//само c должно быть простым и хотябы одно из отстоящих от
//него на 2 должно быть тоже простым
bool twixed(int c) {
if (prime(c))
if (prime(c - 2) || prime(c + 2))
return true;
return false;
}
int main() {
int n, sum, c;
n = sum = c = 0;
while (n <= 0) {
cout << "Введите количество чисел:";
cin >> n ;
cout << endl;
}
for (int i = 0; i < n; i++) {
cout << "Введите " << i+1 << " число:";
cin >> c ;
if (twixed(c))
sum += c;
else cout << "Ошибка: число не является парным\n";
cout << endl;
}
cout << "Сумма парных чисел: " << sum << endl;
return 0;
}
1)простое число -- нечетное число (за исключением числа 2, которое простое). Доказательство очевидно, поскольку все четные кратны двум, а значит уже делимы без остатка хотя бы на двушку.
2)Если число составное, то его можно представить в виде произведения целых a=m*M (1<m<=M); значит корень(a)=корень(m*M), т.е. среднему геометрическому; значит корень(а) лежит между m и M. Поэтому, "забраковать" число как не простое можно выполнив проверки лишь для чисел <= корня от него.
Т.е. первую функцию можно переписать так:
Код:
bool prime(int c) {
if (c < 2) return false;
//четные, кроме 2 -- не простые
if (c == 2) return true;
if (!(c % 2)) return false;
//i<=sqrt(c), тогда i*i<=c
for (int i = 2; i*i <= c; i++)
if (!(c % i)) return false;
return true;
}
if (c < 2) return false;
//четные, кроме 2 -- не простые
if (c == 2) return true;
if (!(c % 2)) return false;
//i<=sqrt(c), тогда i*i<=c
for (int i = 2; i*i <= c; i++)
if (!(c % i)) return false;
return true;
}
Можно еще улучшить алгоритм, учтя, что нечетное число делится на четное с остатком. Действительно, предположим, что верно обратное, тогда нечетное (2m+1) при делении на четное (2n) должно дать целое (k), т.е. (2m+1)/(2n) = k. Это равносильно тому, что (2m+1)=2nk. Но 2nk четное. Получили противоречие: нечетное равно четному.
Вот новый код функции проверки простых чисел:
Если писать функцию не проверки, а генерации простых чисел, то можно использовать:
1)накопление в массиве ранее найденных простых чисел; в дальнейшем можно следующие числа проверять лишь на остаток деления на найденные простые.
2)Если надо найти все простые, меньшие N, то массив хранения для них будет иметь размер корень(N)/2.
Это я нашел в исходнике здесь (см. там ближе к концу страницы).
Можно еще попробовать избавиться от долгой операции взятия остатка, ведь его величина не имеет значения, надо знать просто ноль он или нет.
Вот новый код функции проверки простых чисел:
Код:
#include <cmath>
....
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//c=3, 5 и 7 этот цикл пропустят, но им можно - они простые :)
//один раз корень посчитать быстрее, чем i*i сравнивать с c
int im = (int)sqrt(c) + 1; //+1 чтобы не писать <= im
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
....
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//c=3, 5 и 7 этот цикл пропустят, но им можно - они простые :)
//один раз корень посчитать быстрее, чем i*i сравнивать с c
int im = (int)sqrt(c) + 1; //+1 чтобы не писать <= im
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
Если писать функцию не проверки, а генерации простых чисел, то можно использовать:
1)накопление в массиве ранее найденных простых чисел; в дальнейшем можно следующие числа проверять лишь на остаток деления на найденные простые.
2)Если надо найти все простые, меньшие N, то массив хранения для них будет иметь размер корень(N)/2.
Это я нашел в исходнике здесь (см. там ближе к концу страницы).
Можно еще попробовать избавиться от долгой операции взятия остатка, ведь его величина не имеет значения, надо знать просто ноль он или нет.
Извиняюсь, в последнем варианте косяк (с приведением к int). Правильно так:
Код:
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//c=3 этот цикл пропустит, но ей можно (3-простое)
//один раз корень посчитать быстрее, чем i*i сравнивать с c в цикле
int im = (int)ceil(sqrt(c)) + 1; //+1 чтобы не писать <= im;
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//c=3 этот цикл пропустит, но ей можно (3-простое)
//один раз корень посчитать быстрее, чем i*i сравнивать с c в цикле
int im = (int)ceil(sqrt(c)) + 1; //+1 чтобы не писать <= im;
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
Друзья, вообще-то есть алгоритмы проверки числа на простоту, не прибегающие к делению его на все делители меньшие корня из него. Так, например, можно в приемлемые сроки узнать, является ли число, длиной в 150 символов, простым. Когда-то в школе я реализовывал RSA криптографию как задание на лето по программированию, и там вся логика как раз и строилась на том, что частота простых чисел не падает с увеличением размерности и существования быстрого алгоритма проверки простоты (т.е. "тыкая" наугад в большие числа (лучше не через генератор случайных чисел, т.к. там его псевдослучайность как раз вредит), а затем проверяя их на простоту, можно в приемлемые сроки найти простое число).
Увы, самого алгоритма проверки простоты не помню, но правильное решение - именно такое. Погуглите книгу "Алгоритмы: построение и анализ", издательство МЦНМО, Москва.
Увы, самого алгоритма проверки простоты не помню, но правильное решение - именно такое. Погуглите книгу "Алгоритмы: построение и анализ", издательство МЦНМО, Москва.
Ну, во-первых, там меньше, чем на все. О длинных числах речи не было, и для них скорей всего вы правы.
И главное -- с методами Монте-Карло (вероятностными) есть проблема, часто не тривиальная, вычисления достоверности результатов..
Возможно, в вашем методе достоверность (доверительная вероятность) легко считается, я его не встречал пока.
И главное -- с методами Монте-Карло (вероятностными) есть проблема, часто не тривиальная, вычисления достоверности результатов..
Возможно, в вашем методе достоверность (доверительная вероятность) легко считается, я его не встречал пока.
Для полноты картины -- генерация простых чисел. Пример на C++. Сделал через функторы для разнообразия :)
P.S. Уместно еще вспомнить алгоритм "Решето Эратосфена" с его модификациями. Короче, для оптимизаций простор широкий. Интересная тема (из области метапрограммирования) - генерация/проверка чисел на этапе компиляции.
Код:
//Генерация простых чисел
//=======================
#include <cstdio>
//Класс функтора генератора простых чисел
struct PrimesGen {
void operator()(unsigned* buffer, unsigned count_for_gen) {
if(count_for_gen < 1) return;
buffer[0] = 2; //первое простое = 2
now = 1;
if(count_for_gen == 1) return;
Functor funct(buffer);
for(unsigned i = 3; ; i += 2) { //простые четными не бывают (кроме 2)
funct(i);
if (now == count_for_gen) break;
}
}
private:
static unsigned now;
struct Functor {
Functor(unsigned* buf) : buffer_(buf) {};
void operator()(unsigned num_for_check) {
//делить достаточно только на уже ранее найденные простые
//(на число 2 с индексом 0 тоже можно не делить)
for(unsigned i = 1; i < now; ++i)
if( !( num_for_check % buffer_[i] ) ) return;
buffer_[now++] = num_for_check;
}
private:
unsigned* buffer_;
};
};
unsigned PrimesGen::now = 0;
//класс функтора для печати результата
struct PrintFunctor {
PrintFunctor() : n(1) {}
void operator()(unsigned i) {
printf("#%u: %u\n", n++ , i);
}
private:
unsigned n; //номер простого числа
};
int main() {
const unsigned CNT = 100;
unsigned primes[CNT];
PrimesGen gen;
gen(primes, CNT); //генерация первых 100 простых чисел
//выводим на экран результат:
PrintFunctor pf;
for(unsigned i = 0; i < CNT; ++i) pf(primes[i]);
return 0;
}
//=======================
#include <cstdio>
//Класс функтора генератора простых чисел
struct PrimesGen {
void operator()(unsigned* buffer, unsigned count_for_gen) {
if(count_for_gen < 1) return;
buffer[0] = 2; //первое простое = 2
now = 1;
if(count_for_gen == 1) return;
Functor funct(buffer);
for(unsigned i = 3; ; i += 2) { //простые четными не бывают (кроме 2)
funct(i);
if (now == count_for_gen) break;
}
}
private:
static unsigned now;
struct Functor {
Functor(unsigned* buf) : buffer_(buf) {};
void operator()(unsigned num_for_check) {
//делить достаточно только на уже ранее найденные простые
//(на число 2 с индексом 0 тоже можно не делить)
for(unsigned i = 1; i < now; ++i)
if( !( num_for_check % buffer_[i] ) ) return;
buffer_[now++] = num_for_check;
}
private:
unsigned* buffer_;
};
};
unsigned PrimesGen::now = 0;
//класс функтора для печати результата
struct PrintFunctor {
PrintFunctor() : n(1) {}
void operator()(unsigned i) {
printf("#%u: %u\n", n++ , i);
}
private:
unsigned n; //номер простого числа
};
int main() {
const unsigned CNT = 100;
unsigned primes[CNT];
PrimesGen gen;
gen(primes, CNT); //генерация первых 100 простых чисел
//выводим на экран результат:
PrintFunctor pf;
for(unsigned i = 0; i < CNT; ++i) pf(primes[i]);
return 0;
}
Если интересно, вот пример на C++ проверки числа на простоту на этапе компиляции (из области метапрограммирования). Используется constexpr из стандарта C++11 и static_assert. Подсмотрел в этом источнике. Там есть еще вариант, основанный на шаблонах (годится и в старом стандарте).
Код:
//По материалу:
//"Метапрограммирование с помощью constexpr"
//(http://wincode.org/cpp/metaprogramming-with-constexpr)
#include <cstdio>
//#include <cinttypes>
constexpr bool is_prime_recursive(size_t number, size_t c) {
return (c*c > number) ? true :
(number % c == 0) ? false :
is_prime_recursive(number, c+1);
}
constexpr bool is_prime_func(size_t number) {
return (number <= 1) ? false : is_prime_recursive(number, 2);
}
int main() {
static_assert(is_prime_func(7), "Not prime!"); // compile-time
int i = 7;
if(is_prime_func(i)) // run-time
puts("Prime");
else puts("Not prime");
return 0;
}
//"Метапрограммирование с помощью constexpr"
//(http://wincode.org/cpp/metaprogramming-with-constexpr)
#include <cstdio>
//#include <cinttypes>
constexpr bool is_prime_recursive(size_t number, size_t c) {
return (c*c > number) ? true :
(number % c == 0) ? false :
is_prime_recursive(number, c+1);
}
constexpr bool is_prime_func(size_t number) {
return (number <= 1) ? false : is_prime_recursive(number, 2);
}
int main() {
static_assert(is_prime_func(7), "Not prime!"); // compile-time
int i = 7;
if(is_prime_func(i)) // run-time
puts("Prime");
else puts("Not prime");
return 0;
}