Делимост на седем

[mail_dinko]

Да ви се похваля, т.е. да споделя с тези, които не го знаят (ако изобщо има такива):
В един сайт видях признак за делимост на седем:
1. гледаме си числото
2. задраскваме цифрата на единиците
3. това което е останало от числото го умножаваме по 3
4. към полученото произведение прибавяме цифрата на единиците, която задраскахме
5. ако полученото число се дели на седем, значи първоначално даденото число е кратно на седем
6. ако полученото число не е кратно на седем, то и даденото число не се дели на седем без остатък
7. ако числото, което сме получили е твърде голямо, т.е. не може да преценим дали се дели на седем или не, повтаряме процедурата колкото пъти е необходимо

ПРИМЕР
задача 1. Дели ли се числото 324 на седем?
1. задраскваме единиците - получихме 32
2. 32*3+4=96+4=100
3. задраскваме единиците - получаваме 10
4. 10*3+0=30
5. числото 30 не се дели на седем, следователно 324 не е кратно на седем

задача 2. числото 105 кратно ли е на седем?
1. задраскваме цифрата на единиците - получаваме 10
2. 10*3+5=30+5=35
3. 35 е кратно на седем, следователно и 105 е кратно на седем

[mkmarinov]

Имаше един сайт с признаци за делимост на всички прости числа до 100. Ако си спомня линка, ще го пусна.

[mail_dinko]

за да не пускам нова тема - искам да попитам има ли начин да се разбере дали дадено число е просто без решетото на Ератостен, защото ако числото е голямо става доста бавно цялото задраскване

[Добромир Глухаров]

за да не пускам нова тема - искам да попитам има ли начин да се разбере дали дадено число е просто без решетото на Ератостен, защото ако числото е голямо става доста бавно цялото задраскване

Освен Решето на Ератостен, съществуват редица негови усъвършенствания, например Решето на Сундарам: Ето ТУК.

Ако трябва да се определи дали дадено естествено число [tex]N[/tex] е просто, проверяваме дали се дели на простите числа, не по големи от [tex]\sqrt{N}[/tex]. Ако не се дели на никое от тях, значи е просто.

Може да се използва и Теорема на Уилсън.

[mkmarinov]

За големи числа теоремата на Ойлер-Ферма е по-удобна от тази на Уилсън .
(но тя се ползва по-скоро да докажем, че числото НЕ е просто)

[ganka simeonova]

за да не пускам нова тема - искам да попитам има ли начин да се разбере дали дадено число е просто без решетото на Ератостен, защото ако числото е голямо става доста бавно цялото задраскване

Аз не съм никак добра в теорията на числата , но всяко просто число може да се представи по един от двата начина:
Или като 4к+1, или като 4к-1.
Пример: 13=4.3+1; 19=4.5-1
И още нещо: Всяко число от първия вид винаги е сбор на два точни квадрата, а число от втория вид, никога не може да се представи като такова.

[ptj]

за да не пускам нова тема - искам да попитам има ли начин да се разбере дали дадено число е просто без решетото на Ератостен, защото ако числото е голямо става доста бавно цялото задраскване

Аз не съм никак добра в теорията на числата , но всяко просто число може да се представи по един от двата начина:
Или като 4к+1, или като 4к-1.
Пример: 13=4.3+1; 19=4.5-1
И още нещо: Всяко число от първия вид винаги е сбор на два точни квадрата, а число от втория вид, никога не може да се представи като такова.

По-голяма глупост не можа ли да напишеш? Какви са тези сравнения по модул 4? Ами те ти обхващат всички нечетни числа.

П.П. И това е учител по математика в елитна гимназия...

[amsara]

И защо да е глупост Аз тези теореми, които ги упоменавате всички по-горе, не съм ги и чувала даже. mail_dinko пита как да се открие лесно дали едно число е просто.Ами комбинацията от две отделни представяния на едно число ,веднъж като 4k+1 и още веднъж като сбор от два точни квадрата, наистина докарва гарантирано просто число.Може би госпожата е имала предвид точно това. А не отделно удовлетворяване на само едно от двете условия, защото тогава наистина се получават нечетни числа, сред които има и съставни, не само прости.
Например:
5=4.1+1=2^2+1^2 - просто
9=4.2+1 няма сбор от точни квадрати, следователно е съставно, понеже отговаря само на едното условие
13=4.3+1=3^2+2^2 - просто
17=4.4+1=4^2+1^2 - просто
21=4.5+1 няма сбор от точни квадрати, следователно е съставно, понеже отговаря само на едното условие
и т.н
А за типа 4к-1 не зная как се прави пресяването на прости и съставни.Вероятно и там си има някакво допълнително условие, което ще разкара тия нечетни числа, които не са прости.

[allier]

Това, което Ганка пише е напълно вярно. Всяко просто число, по-голямо от 2, е нечетно и следователно дава остатък 1 или 3 при деление на 4. Това за сума от квадрати също е вярно, но няма нищо общо с простите числа.

Така че ptj преди да приказваш глупости (както винаги), прочети какво е написано и не го интерпретирай по твой си начин.

Сара пък също коментира без да и е станало ясно за какво става въпрос. 9+16 = 25.

[strangerforever]

Написаното от ganka simeonova е напълно вярно, ptj, не го интерпретирай грешно, никъде не е споменато, че това, че едно число може да се представи така, е достатъчно, за да заключим, че е просто.

[ptj]

Това, което Ганка пише е напълно вярно. Всяко просто число, по-голямо от 2, е нечетно и следователно дава остатък 1 или 3 при деление на 4. Това за сума от квадрати също е вярно, но няма нищо общо с простите числа.

Така че ptj преди да приказваш глупости (както винаги), прочети какво е написано и не го интерпретирай по твой си начин.

Сара пък също коментира без да и е станало ясно за какво става въпрос. 9+16 = 25.

Именно, това че простите числа по-големи от 2 са нечетни и учениците в 6-ти клас го знаят. Написаното са празни приказки, не даващи абсолютно никаква информация за начините на намиране на прости числа.

[amsara]

ОК, сгрешила съм и си го признавам Едва ли обаче с това е свършил светът. Нали затова е форумът, ако човек се обажда само, когато е сигурен, че е прав напълно и се страхува да попита или да изкаже твърдение, дори и грешно, за какво му е да е тук.Да, не съм проследила нататък другите числа за да видя какво става със сбора от квадратите.Сега Алиер дали е доволен Посипах си главата с пепел.Болна съм и не съм на даскало ,влязох затова с кеф в мат 10, ама сега с още по-голям кеф ще изляза.Всичко живо следи някой просто да сбърка и да го резне с коментар.И така на всички нива като възраст, от ученици до големите.

[ganka simeonova]

ptj пак прописа и пак не разбира за какво иде реч!
Написах го като свойство, защото на мен ми харесва , а и темата е за прости числа! ( погледни заглавието на раздела).
ptj, с теб се бяхме разбрали да не коментираш мои решения, както и аз твои, за да не стане пак пожар. Както виждаш, аз удържам на обещанието си!

[mkmarinov]

Всичко живо следи някой просто да сбърка и да го резне с коментар.

Определено трябва очевидните грешки да не ги отбелязваме, за да не се сърдят децата.

mail_dinko, ако съществуваше бърз (класически) начин да се види дали дадено число е просто, най-използваните криптографски алгоритми отиват на кино. Обаче съществуват бързи (да се чете: с полиномиална сложност) такива алгоритми за квантови компютри, например алгоритъм на Шор.

[amsara]

Ако пък ми кажеш къде прочете, че съм казала такава глупост да не се отбелязват грешките, ще съм ти много благодарна.
Има разлика между обяснение защо и в какво греши даден човек(в случая аз) и заядливо подметнат коментар за това кой и какво е разбрал или неразбрал и коментирал въпреки това. От обяснението на сгрешеното полза ще има,допусналият грешката едва ли ще я повтори, от коментара едва ли обаче ще има някакъв положителен ефект.Малко ли са случаите на сгрешени решения из форума, дайте вместо да се обяснява по същество грешката да почнем отдолу да викаме как написалият грешното нищо не разбира, но си пише ей така за спорта, разбрал-недоразбрал.Ей, всички понякога грешат или не разбират точно какво се има предвид, толкова ли е трудно да се разбере?Обяснете от позицията на много по-добри, а не коментрайте толкова кой какъв еи какво е направил.Защото, ако в случая грешката ми е очевидна и си я схванах и сама, утре може и да не е толкова набиваща се и вместо коментар да имам нужда някой спокойно да обясни къде точно греша, а не колко съм зле.Това имах предвид, ама пак ми изкривиха думите.

[mkmarinov]

Я кажи къде някой е написал, че си много зле. Май ти изкривяваш думите .

[ganka simeonova]

Предлагам, да уталожим топката

[allier]

Naprotiv, Sara. Az nqmam nishto protiv teb ... Daje se vuzhishtavam na tvoyto uchastie i resheniq na zadachi. No v sluchaya tvoyat post beshe po-skoro komentar otkolkoto reshenie ... Komentar, koito e napisan bez da e razbrano za kakvo tochno stava vupros v posta na Ganka (koqto mejdu drugoto moje, i to mnogo dobre, sama da se zashtitava ot podobni na ptj dosadnici ).

[WEBER]

#include <stdio.h>
void main()
{
int number, i, isprime;
printf("Enter number: ");
scanf("%d",&number);
isprime=1;
for(i=2; i<=number/2; i++)
if((number%i)==0) isprime=0;
if(isprime==1) printf("the number is prime");
else printf("The number is not prime");
}

Ето така се намират прости числа.

[Добромир Глухаров]

Код: Избери целия код

#include <stdio.h>
void main()
{
 int number, i, isprime;
 printf("Enter number: ");
 scanf("%d",&number);
 isprime=1;
   for(i=2; i*i<=number; i++)
      if((number%i)==0) isprime=0;
      if(isprime==1) printf("the number is prime");
      else printf("The number is not prime");
}

Ето така се намират прости числа.

Позволих си една малка поправка - вместо [tex]i<=number/2[/tex] - [tex]i*i<=number[/tex] - така програмата върви по бързо .

[drago]

Има бърз начин да се отговори с ДА/НЕ на въпроса дали дадено число е просто, т.е. алгоритъм с полиномиален брой операции спрямо входа, представяйте си спрямо броя на цифрите на числото. Иначе казано: PRIMES is in P.
Открит е съвсем скоро(2002) и авторите му получават Гьоделова награда за това през 2006.
http://en.wikipedia.org/wiki/AKS_primality_test

Това засега не разклаща криптографията, защото тя се опира по-скоро на това, че няма ефективни алгоритми за разлагане на число на множители.

[mkmarinov]

drago, имаш право, бях объркал двете задачи.

WEBER, я пробвай този алгоритъм с 64 битово число и ми кажи за колко време ще работи. Има оптимизации, които го правят един порядък по-бърз - пак не помагат .

[WEBER]

drago, имаш право, бях объркал двете задачи.

WEBER, я пробвай този алгоритъм с 64 битово число и ми кажи за колко време ще работи. Има оптимизации, които го правят един порядък по-бърз - пак не помагат .

Тоя алгоритъм е пълен боклук, но ще е лесен за разбиране и става за нуждите на темата...

[Добромир Глухаров]

Ето нещо от форума за Информатика - 2008 г.:

http://www.math10.com/informatika/viewtopic.php?t=2984

[anotherone]

За големи числа теоремата на Ойлер-Ферма е по-удобна от тази на Уилсън .
(но тя се ползва по-скоро да докажем, че числото НЕ е просто)

Теоремата на Ферма Ойлер е само необходимо условие числото да е просто но не е достатъчно!Теоремата на Уилсън от друга страна е и необходимо и достатъчно условие числото да е просто.