BOOL IsSimple = true;
for(int x=2; x<=sqrt(N); x++)
if(N%x == 0)
{
IsSimple = false;
break;
}
Простые числа(И вообще отыскание чисел(групп чисел) с наперёд заданными свойствами)
Нужен алгоритм или программа на С по отысканию простых чисел не больше данного и по проверке данного числа на простоту
Если вопрос глупый и избитый,дайте ссылочку на соответствующий источник
Если вопрос глупый и избитый,дайте ссылочку на соответствующий источник
Код по алгоритму "Решето Эратосфена" для поиска простых чисел:
Код:
int finish=99,begin=2;
bool a[finish];
int x,y;
a[1]=false;
for(x=begin;x<=finish;x++){
a[x]=true;
}
for(x=begin;x<=finish/2;x++)
{
for(y=begin;y<=finish/x;y++){
a[x*y]=false;
}
}
for(x=begin;x<=finish;x++)
{
if(a[x])
printf("%d",&x);
}
bool a[finish];
int x,y;
a[1]=false;
for(x=begin;x<=finish;x++){
a[x]=true;
}
for(x=begin;x<=finish/2;x++)
{
for(y=begin;y<=finish/x;y++){
a[x*y]=false;
}
}
for(x=begin;x<=finish;x++)
{
if(a[x])
printf("%d",&x);
}
Цитата:
Originally posted by Denton
Код по алгоритму "Решето Эратосфена" для поиска простых чисел:
Код по алгоритму "Решето Эратосфена" для поиска простых чисел:
СПАСИБО
Теперь только осталось это в С перевести:)
Цитата:
Originally posted by Maxyman
СПАСИБО
Теперь только осталось это в С перевести:)
СПАСИБО
Теперь только осталось это в С перевести:)
Вот мой вариант на С для проверки является ли число простым:
Код:
N - число которое надо проверить на "простоту"
IsSimple - флаг простоты (1 - простое, 0 - не простое)
Значит так.
я написал функцию is_prime,которая определяет простое число или нет и возвращает 0,если число составное и 1,если число простое.
На многочисленных примерах функция работает.
Но если я вызываю is_prime из другой функции,то она возвращает только ноль...
...что я могу делать не так?
Если это важно,я делаю программу на ТурбоС какой-то старой версии,которая даже под Windows не работает.
Заранее спасибо
P.S. только не спрашивайте,почему я программирую именно там и "не там" я программировать не могу
я написал функцию is_prime,которая определяет простое число или нет и возвращает 0,если число составное и 1,если число простое.
На многочисленных примерах функция работает.
Но если я вызываю is_prime из другой функции,то она возвращает только ноль...
...что я могу делать не так?
Если это важно,я делаю программу на ТурбоС какой-то старой версии,которая даже под Windows не работает.
Заранее спасибо
P.S. только не спрашивайте,почему я программирую именно там и "не там" я программировать не могу
исходник покажи
Цитата:
Originally posted by Matush
исходник покажи
исходник покажи
Код:
#include<stdio.h>
#define yes 1
#define no 0
int num=0;
int is_prime (int);
void goldbach_conjecture (int);
void closest_primes (int);
int main(void){
while(num<3) {
printf("\n\n%15s\n\n\n"," Enter an
integer number bigger than 2");
if ( (scanf("%d",&num))!=1)
{
printf("\n\n%20s\n\n\n","Invalid
input!!!");
return 1;
}
else
if (num >2 ) {break;}
}
if ((is_prime (num))==yes)
{
printf("\n\n%15d%5s\n%5d%3s
%3d\n\n\n",num,
" is a prime number");
}
else
{
printf("\n\n%15d%5s\n\n\n",num,
" is not a prime number");
}
if (num%2==1)
{
printf("\n\n%8s\n\n\n",
"GOLDBACH CONJECTURE:
impossible");
}
else {
goldbach_conjecture(num);
}
closest_primes (num);
return 0;
}
int is_prime (int n1)
{
int counter=2;
while(num%counter!=0)
{
++counter;
}
if (counter>=n1)
return yes;
return no;
}
void goldbach_conjecture (int n2)
{
printf("\n\n%15s%d%\n20s","The Goldbach
conjecture
of even number ",
n2," has to be here");
return; }
void closest_primes (int n3)
{
printf("\n\n%15s%d\n%20s\n","The calculation of closest primes of ",
n3," has to be here");
return;
}
#define yes 1
#define no 0
int num=0;
int is_prime (int);
void goldbach_conjecture (int);
void closest_primes (int);
int main(void){
while(num<3) {
printf("\n\n%15s\n\n\n"," Enter an
integer number bigger than 2");
if ( (scanf("%d",&num))!=1)
{
printf("\n\n%20s\n\n\n","Invalid
input!!!");
return 1;
}
else
if (num >2 ) {break;}
}
if ((is_prime (num))==yes)
{
printf("\n\n%15d%5s\n%5d%3s
%3d\n\n\n",num,
" is a prime number");
}
else
{
printf("\n\n%15d%5s\n\n\n",num,
" is not a prime number");
}
if (num%2==1)
{
printf("\n\n%8s\n\n\n",
"GOLDBACH CONJECTURE:
impossible");
}
else {
goldbach_conjecture(num);
}
closest_primes (num);
return 0;
}
int is_prime (int n1)
{
int counter=2;
while(num%counter!=0)
{
++counter;
}
if (counter>=n1)
return yes;
return no;
}
void goldbach_conjecture (int n2)
{
printf("\n\n%15s%d%\n20s","The Goldbach
conjecture
of even number ",
n2," has to be here");
return; }
void closest_primes (int n3)
{
printf("\n\n%15s%d\n%20s\n","The calculation of closest primes of ",
n3," has to be here");
return;
}
конкретные функции goldbach_conjecture и
closest_primes... я писал по всякому. Потом просто стёр и вставил цикл while со счётчиком ,который перебирает натуральный ряд и проверяет числа на простоту... всегда получался 0
P.S. По-моему,эту тему лучше перенести в раздел "Студентам"
Чего-то не пойму.
Функция is_prime работает.
Но ее было бы лучше сделать такой:
P.S. Зачем printf("\n\n%15d%5s\n%5d%3s% - так много выводов чисел, когда выводиш только одно?
Функция is_prime работает.
Но ее было бы лучше сделать такой:
Код:
int is_prime (int n1)
{
for(int x=2; x<=sqrt(n1); x++)
if(n1%x == 0)
return no;
return yes;
}
{
for(int x=2; x<=sqrt(n1); x++)
if(n1%x == 0)
return no;
return yes;
}
P.S. Зачем printf("\n\n%15d%5s\n%5d%3s% - так много выводов чисел, когда выводиш только одно?
Цитата:
Originally posted by Matush
Чего-то не пойму.
Функция is_prime работает.
Но ее было бы лучше сделать такой:
P.S. Зачем printf("\n\n%15d%5s\n%5d%3s% - так много выводов чисел, когда выводишь только одно?
Чего-то не пойму.
Функция is_prime работает.
Но ее было бы лучше сделать такой:
Код:
int is_prime (int n1)
{
for(int x=2; x<=sqrt(n1); x++)
if(n1%x == 0)
return no;
return yes;
}
{
for(int x=2; x<=sqrt(n1); x++)
if(n1%x == 0)
return no;
return yes;
}
Код:
int is_prime (int n1)
{
int counter=2;
while(num%counter!=0)
{ ++counter; }
if (counter>=n1)
return yes;
return no;
}
{
int counter=2;
while(num%counter!=0)
{ ++counter; }
if (counter>=n1)
return yes;
return no;
}
P.S. Зачем printf("\n\n%15d%5s\n%5d%3s% - так много выводов чисел, когда выводишь только одно?
спасибо большое....твой варианьт гораздо красивее
насчёт принтф,просто я немножко "подстриг" текст,но не всё убрал,похоже....
но всё-таки остаётся вопрос,почему функция не работает при её вызове из других функций,кроме мэйн ? Да ладно уж...
Цитата:
Originally posted by Maxyman
но всё-таки остаётся вопрос,почему функция не работает при её вызове из других функций,кроме мэйн ? Да ладно уж...
но всё-таки остаётся вопрос,почему функция не работает при её вызове из других функций,кроме мэйн ? Да ладно уж...
Как это не работает?
Приведи небольшой кусок кода в котором моя вышепреведенная функция будет давать неверный результат.
лучше делить не на все числа , а на найденные ранее простые.
Цитата:
Originally posted by koderAlex
лучше делить не на все числа , а на найденные ранее простые.
лучше делить не на все числа , а на найденные ранее простые.
Ну для этого надо эти числа иметь.
Функция int is_prime(int); - как можем судить из ее названия, служит для проверки конкретного числа на простоту.
Но если Тебя это немного успокоит, вот в два раза облегченная версия:
Код:
int is_prime (int n1)
{
if(n1%2 == 0)
return no;
for(int x=3; x<=sqrt(n1); x+=2)
{
if(n1%x == 0)
return no;
}
return yes;
}
{
if(n1%2 == 0)
return no;
for(int x=3; x<=sqrt(n1); x+=2)
{
if(n1%x == 0)
return no;
}
return yes;
}
Цитата:
Originally posted by Matush
Как это не работает?
Приведи небольшой кусок кода в котором моя вышепреведенная функция будет давать неверный результат.
Как это не работает?
Приведи небольшой кусок кода в котором моя вышепреведенная функция будет давать неверный результат.
Функция goldbach_conjecture,которая, в соответствии с гипотезой Гольдбаха,что любое чётное число можно представить в форме двух простых слагаемых, должна искать эти самые слагаемые:
Код:
void goldbach_conjecture (int n2)
{
int k;
for (k=2;k==n2/2;k++)
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
{ printf("\n\n%15s\n%3d%3s%3d%3s\n",
"The Goldbach Conjecture: ",n3,"=",k,"+",n3-k); }
return; }
{
int k;
for (k=2;k==n2/2;k++)
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
{ printf("\n\n%15s\n%3d%3s%3d%3s\n",
"The Goldbach Conjecture: ",n3,"=",k,"+",n3-k); }
return; }
for (k=2;k==n2/2;k++)
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
САмое интересное,что я самыми разными способами пытаюсь сделать цикл типа:
И этот цикл ни разу не запускается(кроме do...while,где он один раз исполняется),вот хоть убей,ошибку не нахожу
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
САмое интересное,что я самыми разными способами пытаюсь сделать цикл типа:
Код:
к=2
a=n2-k
выполнять цикл пока к>a или к<n/2 /*неважно в принципе*/
действие
к++
a=n2-k
выполнять цикл пока к>a или к<n/2 /*неважно в принципе*/
действие
к++
И этот цикл ни разу не запускается(кроме do...while,где он один раз исполняется),вот хоть убей,ошибку не нахожу
Цитата:
Originally posted by Maxyman
Нужен алгоритм или программа на С по отысканию простых чисел не больше данного и по проверке данного числа на простоту
Если вопрос глупый и избитый,дайте ссылочку на соответствующий источник
Нужен алгоритм или программа на С по отысканию простых чисел не больше данного и по проверке данного числа на простоту
Если вопрос глупый и избитый,дайте ссылочку на соответствующий источник
Ты можешь четко сформулировать что тебе нужно? Тебе два варианта показали (исходники) - правильные. Что тебе нужно сделать?
Цитата:
Originally posted by Neutral
Ты можешь четко сформулировать что тебе нужно? Тебе два варианта показали (исходники) - правильные. Что тебе нужно сделать?
Ты можешь четко сформулировать что тебе нужно? Тебе два варианта показали (исходники) - правильные. Что тебе нужно сделать?
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
Цитата:
Originally posted by Maxyman
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
ему всё равно массив простых чисел удобнее иметь .
Цитата:
Originally posted by Maxyman
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
3. Ну тебе нужно либо завести масив простых либо просто проверять все пары(будет долго работать).
4. Как мне кажеться лучше идти вправо и влево от того числа и проверять.
Если надо могу написать реализацию всего, как я понял тебе на C надо.
Цитата:
Originally posted by Neutral
3. Ну тебе нужно либо завести масив простых либо просто проверять все пары(будет долго работать).
4. Как мне кажеться лучше идти вправо и влево от того числа и проверять.
Если надо могу написать реализацию всего, как я понял тебе на C надо.
3. Ну тебе нужно либо завести масив простых либо просто проверять все пары(будет долго работать).
4. Как мне кажеться лучше идти вправо и влево от того числа и проверять.
Если надо могу написать реализацию всего, как я понял тебе на C надо.
дай пожалуйста,а то у меня 4-я и 3-я функции,вообще не работают
Цитата:
Originally posted by Maxyman
[
[
Код:
void goldbach_conjecture (int n2)
{
int k;
for (k=2;k==n2/2;k++)
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
{ printf("\n\n%15s\n%3d%3s%3d%3s\n",
"The Goldbach Conjecture: ",n3,"=",k,"+",n3-k); }
return; }
{
int k;
for (k=2;k==n2/2;k++)
if (is_prime(k)==yes && is_prime(n3-k) ==yes)
{ printf("\n\n%15s\n%3d%3s%3d%3s\n",
"The Goldbach Conjecture: ",n3,"=",k,"+",n3-k); }
return; }
И скажите ещё,пожалуйста,почему этот цикл не работает,при условии,что is_prime(int n2)написана правильно
Цитата:
Originally posted by Maxyman
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
Я-чайник и хотел сделать самостоятельно,или хотя бы с чьей-то помощью,чтоб хоть что-то уметь,
но,если интересно,то задание следующее:
1. Вводится число,проверяется на простоту.(с этим справился)
2.Если число составное,разложить на простые множители(с этим справился без использования первой функции)
3.Если число чётное-найти все варианты разложения на 2 простых слагаемых(гипотеза Гольдбаха).
4 И,наконец,найти ближайшие к данному числу простые числа сверху и снизу.
"3" и "4" пытался делать с помощью "1" и ничего не выходит.
В четвёртом варианте либо ничего не получалось,либо выводилось 2 числа-одно наединицу больше.другое на единицу меньше,либо зацикливалось всё...
Вот как приблизительно могло выглядеть решение:
#include <stdio.h>
#include <math.h>
int is_prime(int x)
{
int i;
if (x<2) return 0;
if (x==2) return 1;
if ((x%2==0) && (x!=2)) return 0;
else
{
for (i=3; i<=(int)(sqrt(x)); i+=2)
{
if (x%i==0) return 0;
}
}
return 1;
}
void canon(int x)
{
if (x<2) return;
int q=x,c=3,stc=0;
while (q%2==0) {stc++; q=q/2;}
if (stc!=0) printf("2^%d",stc);
if ((q!=1) && (stc!=0)) printf("*");
while (q!=1)
{
stc=0;
while (q%c==0) {stc++; q=q/c;}
if (stc!=0) printf("%d^%d",c,stc);
if ((q!=1) && (stc!=0)) printf("*");
c+=2;
}
printf("\n");
}
void goltdbah(int x)
{
if (x<2) return;
int i;
if (is_prime(x-2)) printf("2 %d\n",x-2);
for (i=3; i<=x/2; i+=2)
{
if (is_prime(i) && is_prime(x-i)) printf("%d %d\n",i,x-i);
}
}
void near_prn(int x)
{
if (x<2)
{
printf("Bigger prime - 2\n");
printf("Smaller prime - none\n");
return;
}
if (x==2)
{
printf("Bigger prime - 3\n");
printf("Smaller prime - none\n");
return;
}
int i,bigger=0,smaller=0;
for (i=1; (!bigger || !smaller); i++)
{
if (is_prime(x-i)==1) smaller=x-i;
if (is_prime(x+i)==1) bigger=x+i;
}
printf("Bigger prime - %d\n",bigger);
printf("Smaller prime - %d\n",smaller);
}
int main()
{
int n;
printf("Input number:\n");
scanf("%d",&n);
if (is_prime(n)) printf("Yes, %d - is prime\n",n); else printf("No, %d - is not prime\n",n);
if (is_prime(n)==0) canon(n);
if (n%2==0) goltdbah(n);
near_prn(n);
}
Вроде все просто и понятно, но если есть вопросы - пиши отвечу. Удачи!
Цитата:
Originally posted by Neutral
Вот как приблизительно могло выглядеть решение:
Вроде все просто и понятно, но если есть вопросы - пиши отвечу. Удачи!
Вот как приблизительно могло выглядеть решение:
Вроде все просто и понятно, но если есть вопросы - пиши отвечу. Удачи!
спасибо,у меня примерно тоже самое.
Скомпилирую,проверю на работоспособность и буду сравнивать в чём разница
Цитата:
Originally posted by Maxyman
И скажите ещё,пожалуйста,почему этот цикл не работает,при условии,что is_prime(int n2)написана правильно
И скажите ещё,пожалуйста,почему этот цикл не работает,при условии,что is_prime(int n2)написана правильно
Ну так, внимательнее надо быть.
Что то мне не очень нравится выражение в for - "k==n2/2". Из за него для всех n2 кроме 4 цикл точно ни разу не выполнится.
Далее, по тексту присутствует n3. Это что? Глобальная переменная или опечатка? Может там все-таки n2?
Цитата:
Originally posted by Maxyman
И скажите ещё,пожалуйста,почему этот цикл не работает,при условии,что is_prime(int n2)написана правильно
И скажите ещё,пожалуйста,почему этот цикл не работает,при условии,что is_prime(int n2)написана правильно
== опечатка,а n3-глобальная опечатка...
спасибо...