ברגע שמס' אינו מתחלק ב2 ואינו מתחלק ב3 הוא ראשוני, לא?

מספר ראשוני הוא מספר שמתחלק רק בעצמו וב-1.

עבור X, תבדוק אם הוא מתחלק ב2 עד החלק_השלם(שורשX)- אם הוא מתחלק בלפחות אחד מהם, הוא לא ראשוני, אחרת, הוא ראשוני.

Any sufficiently advanced bug is indistinguishable from a feature

המס' 17
לבדוק אם הוא מתחלק מ2 עד השורש שלו?

כדי לבדוק אם מספר הוא ראשוני צריך לבדוק אם הוא מתחלק במספר כלשהו ללא שארית חוץ מ1 ועצמו.

אבל מספיק לבדוק אם הוא מתחלק במס' כלשהו בין 2 לבין החלק השלם של שורש המס'.
לדוגמא
כדי לבדוק את המס 453 מספיק לבדוק בין 2 ל 21

קיימת אופציה נוספת וזה לבדוק חלוקה רק בגורמים ראשונים שגם זו בדיקה מספקת.

קוד:

 

int Prime(int x){
for (int i=2;i<sqrt(float(x));++i)
	if (x%i == 0)
	 return 0;
return 1;
}

אם המספר ראשוני, יוחזר 1, אחרת, 0.

Any sufficiently advanced bug is indistinguishable from a feature

זה יותר מדוייק.

Any sufficiently advanced bug is indistinguishable from a feature

#include <stdio.h>
#include <conio.h>
#include <math.h>
int prime (int x);
void main (void)
{
float x;
clrscr();
printf ("give x=");
scanf ("%d", &x);
if (prime(x)==1)
printf ("rishoni");
else
printf ("lo rishoni");
getch();
}

int prime (int x)
{
int i;
for (i=2; i<sqrt(x); i++)
if (x%i==0)
return 0;
else
return 1;
}

כל מספר שאני אכניס, התוכנית אומרת שהוא לא ראשוני
מדוע ? כיצד לתקן זאת ?
תודה רבה מראש

כי הפונקציה שכתבת לא נכונה. תעתיק את הפונקציה שכתבתי לך..
(ראשית, אתה עושה if...reutrn0 ELSE return 1, לא צריך להיות else, כי אז בכל מקרה התוכנית בודקת עם המספר מתחלק ב2 (הריצה הראשונה), ומחזירה 1 אם הוא אי זוגי, ו0 אם הוא זוגי., מה שאתה רוצה, זה לבדוק האם המספר מתחלק במספר כלשהו בטווח 2-שורשX, אם כן - אז אתה ישר יודע שהוא לא ראשונה ועושה return 0;, אבל אם הלולאה מסתיימת, זה אומר שזה לא יצא מהפונקציה עם return0 , אז במילא שמים בסוף הפונקציה return 1; - למקרה הזה, שהוא ראשוני.
חוץ מזה sqrt מקבל float, חלק מהמהדרים לא מקבלים int כ"מקרה פרטי" של float" אז צריך , כמו שעשיתי, לעשות sqrt(float(x)))

Any sufficiently advanced bug is indistinguishable from a feature

כי בפעם הראשונה שהוא בודק יענו I=2 אז הוא כבר מחזיר את התשובה שים לב ! שרושמים RETUREN אז זה מסיים את הפונקציה והוא לא מבצע לך את כל הלולאה.

חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

Any sufficiently advanced bug is indistinguishable from a feature

למה אתה אף פעם לא דואג ליעילות??...

קוד:

 int Prime(int x){
float num_root=sqrt(float(x));
for (int i=2;i<num_root;++i)
	if (x%i == 0)
	 return 0;
return 1;
}

מה הקשר ליעילות? אם כבר, שלך ייקח עוד כמה אלפיות שנייה יותר.

Any sufficiently advanced bug is indistinguishable from a feature

שלי יהיה יותר קצר עבור כל מספר גדול משלוש בערך....אתה מחשב כל פעם מחדש את השורש, וסתם מבזבז זמן, כי זה פעולה ארוכה.

זה לא מחשב כל פעם מחדש את השורש. בלולאת FOR, בC תקני המהדר מקצה בזיכרון מקום ושומר את הערך ההתחלתי של המשתנה הרץ, ואת הערך של התנאי, לכן גם אי אפשר לשנות את זה בזמן לולאה (שוב, אני מכיר מהדרים שמרשים את זה, אבל זה לא תקני) ז"א זה מחשב את השורש רק בריצה הראשונה.

Any sufficiently advanced bug is indistinguishable from a feature

אם המהדר היה שומר את הערך של התנאי, כל לולאה הייתה אינסופית. תחשוב על השטויות שאתה אומר לפני שאתה כותב אותן...כל איטרציה מחושב מחדש השורש כדי לדעת אם התנאי מתקיים.

אוקיי, אתה מכיר את התקן של C? סבבה, אתה יודע שלולאת FOR, חייבת, תקנית, להיות מהצורה

קוד:

For (Var1=<value/const/defined variable>; i >/</= <value/const/defined var>; f(i))

זה התקן, וככה המהדר מעוצב לחשב את זה (לעומת זאת, בwhile למשל, המהדר תקנית צריך לבדוק בכל פעם מחדש את כל התנאי), אני יודע, שבחלק מהמדרים הלא תקניים כמו visual cpp
או turbo c (כן, הם לא תקניים ב100%) המהדר מאפשר לכתוב איזה תנאי שהוא רוצה, ולא רק תנאי סדר....

אני אמנם סטודנט למתמטיקה, אבל חבר שלי סטודנט למדמ"ח - ובזמנו הוא כתב במסגרת קורס מסויים קומפיילר לC, באסמבלר-וכך הוא כתב את זה, לפי התקן - שFOR לא מקבל בתנאי פונקציה שמקבלת ערך משתנה נוסף, חוץ מהמשתנה הרץ עצמו.

מבין?

Any sufficiently advanced bug is indistinguishable from a feature

במהדר ה"תקני" שלך ותראה מה יצא:

קוד:

 

 
int i,x=1;
 
for(i=100;x<i,--i)
		++x;
 
printf("%d",x);

, ותדע שטעית =)

אסור לעשות את זה.
ברוב השפות לולאת FOR בכלל לא מקבלת תנאי, אלא זה רק משהו בסגנון for i=x to y do
בC, לפי התקן - מותר בכל פעל להפעיל פונקציה על i, אבל אסור שהערך שi מושווה אליו (וזה חייב להיות תנאי השוואה פשוט, לפי התקן) ישתנה...

כמו שאמרתי אני יודע ש visual cpp וturbo c מריצות את זה, ומאפשרות לשנות...וזה יעבוד, נסה את זה בgcc

Any sufficiently advanced bug is indistinguishable from a feature

איך אתה מסביר את זה? ואיך אתה מסביר את הציטוט שהביאו שם לפי ANSI,?

ניסית בgcc?
לגבי הציטוט...אמרתי שזה מוכיח מספיק, וביקשתי סליחה על הטעות.
למרות... שעדיין, החבר שהזכרתי שכתב את המהדר, לפי תקן, כתב את זה בדיוק ככה (אני עברתי על הקוד שלו בזמנו..) והוא קיבל על העבודה במסגרת הקורס, ציון 10.
וgcc לא אמור להריץ את זה, אני זוכר שכתבתי קוד ארוך מאוד, בgcc, והיה לי באג ואחרי שעות של דיבאגינג - גיליתי שזאת בדיוק היתה הבעיה.

Any sufficiently advanced bug is indistinguishable from a feature

רק על זה שחבר שלך עשה מהדר ל C באסמבלי זה ציון 10...
אסמבלי זה איכסה של שפה לעשות בה דברים גדולים, אני כבר מורגל לנוחות שב C/C++

טוב, כולם עושים את זה במדמ"ח בבר אילן, אני לא מצליח להזכר בשם הקורס...
טוב, אני לא צריך לזכור, אני בתואר במתמטיקה והוא בתואר במדמ"ח, מדמ"ח על הז*ן שלי...

Any sufficiently advanced bug is indistinguishable from a feature

כתבתי ככה יותר מפעם אחת ו-gcc קימפל את זה כמו גדול

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://www.fresh.co.il/scripts/birthday.php?date=27/04/1986]

#include <stdio.h>
#include <conio.h>
#include <math.h>
int prime (int x);
void main (void)
{
float x;
clrscr();
printf ("give x=");
scanf ("%d", &x);
if (prime(x)==1)
printf ("rishoni");
else
printf ("lo rishoni");
getch();
}

int prime (int x)
{
for (int i=2; i<sqrt(float(x)); i++)
if (x%i==0)
return 0;
return 1;
}

תשנה את ה float x; בפונקציה הראשית ל int x;
(prime מקבלת אינטג'ר)

Any sufficiently advanced bug is indistinguishable from a feature

קוד PHP:

 int reshoni(int n, int b=2) { 
if (n=b)
return 0;
else {
 if (n%b=0)
 return reshoni(n,b+1)+1;
}
} 


-פעם היה מעט מידע ובאיכות, היום יש המון מידע ובשיטחיות.

אם רוצים לשפר יעילות אז עדיף לעשות ככה:

קוד:

for (int i = 2; i < max; i++)
it will be better to do:
for (int i = 3; i < max; i+=2)

ועל ויכוח היעילות:
אין כזה דבר לשמור את הערך של התנאי...
אם הקומפיילר הוא טוב מאוד(מאוד!) הוא אולי יוכל בדרך פלא להבין ש: sqrt(X) יהיה תמיד אותו מספר אבל אני לא הייתי סומך על הקומפיילר שלי שיבין את זה כי זה מסובך מאוד ועדיף פשוט לעזור לו ולהיות בטוחים מאשר ללכת על סיכון שאולי לא יצליח ואז במקום שפעולה תתבצע פעם אחת היא תתבצע כל פעם(הרבה הרבה יותר איטי).
ואם היית חושב על זה קצת היית מבין שאם הלולאה של הfor הייתה מקבלת אך ורק קבועים אז הוא לא היה (כנראה) נותן לפונקציה להיות שם. תחשוב כמה קשה לחזות מה תיתן הפונקציה אבל אני כמעט בטוח שכל קומפיילר יתן לך לבצע פעולות כאלו גם אם זה לא ANSI.

הוא לא "יודע" שזאת פונקציה שם, הוא רק מקבל ערך. תקנית, אם הערך משתנה - זה לא אכפת לו, הוא עדיין ירוץ, עם הערך הראשון שהפונקציה החזירה..

באמת יש הרבה מהדרים שלא עושים את זה, אני יודע שgcc כן עושה את זה ...

אהא וכן
בקשר ל"ייעול" שכתבת (zivbr)....זה לא יעבוד אם X=2^n כאשר n טבעי. שהרי ברור שX לא ראשוני, אבל לא קיים i אי זוגי (אתה עובר רק על האי זוגיים הגדולים או שווים ל3 וקטנים מmax) שמחלק אותו....כלומר, הוא יחזיר שX ראשוני.

Any sufficiently advanced bug is indistinguishable from a feature

לא לפי מה שאני רואה....

קוד:

A for loop is of the form: 
for (expression1; expression2; expression3) {
		body
	}
Expression1 initializes the loop. It is executed the first time it is encountered.
*** Expression 2 is executed each time prior to entering the body of the loop (like the condition in a while loop). ***
Expression3 is executed immediately after the statements in the body of the loop.

לפי מה שהם כותבים הבדיקה מתבצעת כל פעם מחדש...

אוקיי. זה עכשיו הפיל אותי...לא רק שgcc מתנהג כמו שאמרתי (והוא של לינוקס)
גם חברי הנ"ל, שכתב את המהדר בצמוד לתקן במסגרת האוניברסיטה, כתב את זה בצורה כזאת.

בכל אופן..זה מספיק משכנע :/, סליחה maxim m

Any sufficiently advanced bug is indistinguishable from a feature

#include <stdio.h>
#include <conio.h>
#include <math.h>
int Prime (int n);
void main (void)
{
int n;
clrscr();
printf ("give n=");
scanf ("%d", &n);
if (Prime(n))
printf ("rishnoi");
else
printf ("lo rishoni");
getch();
}

int Prime (int n)
{
int i, flag;
for (i=2; i<sqrt(n); i++)
{
if (n%i==0)
flag=0;
else
flag=1;
};
return flag;
}

יש לי שאלה בנוגע לאלגוריתם שלכם... לא היה לי כוח להתעמק בעניין - אבל מה עם החלק השלם של השורש של המספר קטן מ 2? (למשל 3 הוא מספר ראשוני ולמיטב ידיעתי השורש שלו קטן מ 2..)

ולכן הוא לא יכנס בכלל ללולאה , וישר יאמר שזה מספר ראשוני - 1-3 הם גם ככה מספרים ראשונים.

חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

אה ומה עם 4?

עריכה: כן אני מודע שרק צריך להוסיף "או שווה" בתנאי..

4 או לא מספר ראשוני וברגע שהוא יכנס ללולאה ( כמובן שצריכים להשים שווה ) הוא יבדוק את המספר 2 ויראה שהוא מתחלק בו ואז הוא פשוט יעביר את מצב הדגל ל-1 או 0 בהתאמה שאומר שהמספר אינו ראשוני.

חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

לא קראתי את הסוגריים ^^ my bad

למרות שאני חושב שהוא צריך כן להיות אחרי הכל הוא מתחלק באחד ובעצמו.. מבחינה לוגית אני לא רואה שום בעיה.. הכל עניין של הגדרות שרירותיות.

מספר ראשוני מוגדר באופן הבא
מספר ראשוני הוא מספר שלם חיובי שמתחלק בדיוק בשני מספרים.

1 מתחלק במספר אחד - הוא עצמו ולכן אינו ראשוני.


אם תגדיר שמספר ראשוני הוא מספר שמתחלק בשני גורמים לכל היותר אז 1 יהיה "ראשוני" אבל הוא עדין לא יהיה ראשוני לפי ההגדרה המקובלת.

לא מדובר פה רק בהגדרה שרירותית. למספרים ראשוניים יש תכונות מסויימות, בלי קשר לכמות המחלקים שלהם. 1 לא מקיים לא את ההגדרה, ולא את התכונות, ולכן הוא בשום אופן אינו ראשוני.

מספר p במונואיד (Z,*) (חוג השלמים) נקרא ראשוני אם ורק אם p לא סינגולרי ואם עבור כל v,u E Z =>
p|uv אם ורק אם p|v או p|u.
1 הוא איבר סינגולרי בZ, לכן הוא לא ראשוני.
עכשיו למה צריך הוא לא יהיה סינגולרי? כי p הוא מספר בלתי פריק (רוצים לשמור על ההגדרה שרק מספר שאינו ראשוני יכול להיות מוצג ככפל של מספרים ראשוניים) לכן מספר ראשוני הוא תמיד בלתי פריק (v בלתי פריק אם"ם לא קיימים u,w E D (חוג שלמות) לא סינגולריים כך ש v=uw).
שהרי נניח בשלילה שp פריק וראשוני אזי p=vu וp|v או p|u נניח ללא הגבלת הכלליות שp|v אזי v=pa
=> p=pau => au=1 כלומר u הפיך בסתירה.

Any sufficiently advanced bug is indistinguishable from a feature

זאת הוכחה שאני מוכן לקבל

כי לי הגדירו מספר ראשוני רק בתנאי שהוא מתחלק באחד ובעצמו .. לא אמרו שהם חייבים להיות שונים או שום דבר אחר

ם_O הייתי שמח אם זה היה מובן לפשוטי העם בשפה העברית כי אני לא הצלחתי להבין את רוב ההסבר, אם אתה מסביר משהו תנסה בבקשה שאנשים באמת יבינו ואל תכתוב סימנים ודברים לתואר במתמטיקה כשיש פה אנשים שעוד לא סיימו תיכון.
אם תנסח את זה בצורה מובנת אני אודה לך

מקודם הגדרתי ראשוני תחת כל חוג שלמות, לאו דווקא חוג השלמים Z.
בכל אופן, נניח ש1 או -1 היו ראשוניים, אז גם כל מספר p ראשוני היה אפשר לייצג כמכפלה של 2 מספרים ראשוניים - p=1*p, בגלל שאיבר היחידה תמיד הפיך (סינגולרי, ובZ, האיברים 1 ו-1 הם ההפיכים היחידים [ xy=1 מעל Z רק x=y=+/-1 פותר])
ולמען ש"רק מספר שאינו ראשוני יכול להיות מיוצג ע"י כפל של מספר מספרים ראשוניים"
אומרים שמספר a הוא בלתי פריק רק אם קיימים באותו חוג שלמות b,c לא הפיכים (במקרה של Z, שאינם 1 או מינוס 1) כך ש a=bc.
לכן, אם 1 לא ראשוני, לא תוכל להגיד שp ראשוני יכול להיות מיוצג ככפל של 2 ראשוניים. (או פריק..)

Any sufficiently advanced bug is indistinguishable from a feature

תחפש שמה

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://www.fresh.co.il/scripts/birthday.php?date=07/05/1993&.jpeg]

אתה בטח מתכוון לכך שp ראשוני אם ורק אם p-1 עצרת + 1 מתחלק בp. (אם מישהו רוצה הוכחה..די פשוט)
אם אתה רוצה להשתמש בזה ליותר מבערך לבדוק עם 91 ראשוני..תצטרך מחשב על.

Any sufficiently advanced bug is indistinguishable from a feature

זו הפקודה :

#include<stdio.h>

void main()
{

int i,j,flag=0;

printf ("enter number : \n");

scanf_s("%d",i);

for (j=2;j*j<i;j++)

{

if (i%j==0)

flag=1;

if (i%j==5)

flag=1;

if (i%j==2)

flag=1;

if (i%j==3)

flag=1;

}

if (flag==1)

printf("null\n");

else

printf("rishoni");

}

וקיבלתי הודעת שגיאה של
uninitialized local variable 'i' used
לא ברור לי למה אפשר סבר?

את רוצה לפתוח אשכול חדש, ולא להקפיץ אחד מ 2006?
ולהשתמש בתגית CODE ?