مشکل زمان ؟؟

[Chio-nega-mikoni]

سلام
این یک سوال ساده هست که مال مسابقات کدکاپ بوده.........
سوال بسیار ساده هست ولی وقتی برنامه رو مینویسم بخاطر مشکل زمان نمره کم میارم ..............
محدودیت زمان 0.5 ثانیه هس
لطفا اگر بلدید جواب بدید.........
فایل های سوال و برنامه ای که نوشتم هس..............
شیوه ی صحیح الگوریتمشو میخام..... :متفکر:



tnx


زیرعدد اول
عدد فوق اول عددی است که هر زیر عدد سمت چپ آن اول باشد. برای مثال ۷۳۳۱ فوق اول است. چون
اعداد ۷ و ۷۳ و ۷۳۳ و ۷۳۳۱ اول هستند. اولین عدد فوق اول، عدد ۲ است .
برنامهای بنویسید که با گرفتن عدد nn از ورودی، nn اُمین عدد فوق اول را در خروجی بنویسد .
محدودیتها
عدد خروجی در متغیر صحیح ۴ بایتی قابل ذخیره است .
 زبان C و C++‎‎‎‎‎‎‎‎‎‎
o محدودیت زمان: ۵۰۰ میلیثانیه
o محدودیت حافظه: ۱۵۰ مگابایت
 زبان پایتون و جاوا
o محدودیت زمان: ۱ ثانیه
o محدودیت حافظه: ۲۰۰ مگابایت
مثال
نمونه ورودی
5
نمونه خروجی
23










#include <iostream>
#include <math.h>


using namespace std;




int tet(int);
int aval (int,int);
int avalaval(int);




//main


int main() {
int n,a,b;
a=2;
b=0;
cin >> n;
while (b!=n) {
if(aval(a,0)==1 && avalaval(a)==1)
b++;
a++;
}
cout << a-1 ;
}


//tadad argham


int tet(int r){
int o=0;
while (r!=0){
r = r/10;
o++;
}
return o;
}




//tashkhis


int aval (int r,int k){
int t,c;
c=pow(10,k);
r=(r/c);
if(r==1){
return 0;
}
for (int i=2;i<=(sqrt(r));i++){
if(r%i==0){
return 0;
}
}
return 1;
}




//fooq aval


int avalaval(int r) {
int k,x;
x=0;
k=tet(r);
for (k-1;k>=0;k--){
if(aval(r,k)!=1){
x=1;
break;}
}
if(x==1)
return 0;
else
return 1;
}

[Chio-nega-mikoni]

کسی بلد نبود این رو به ما یاد بده ؟؟؟ :ناراحت::ناراحت::ناراحت::نار� �حت::ناراحت:

[1-9-7-2]

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

int tet (int);
int avalaval (int);
int aval (int, int);

int main () {
int x=1, n=5;
do if (avalaval(x)) --n;
while (n>0 && ++x);
printf ("Elapsed time=%ld\nOutput=%d", clock(), x);
return (EXIT_SUCCESS);
}

int tet (int r) {
int i=0;
while (r!=0 && ++i)
r/=10;
return (i);
}

int aval (int r, int i) {
if ((r/=(int)pow(10, i)) == 1)
return (0);
for (i=2; i <= (sqrt(r)); ++i)
if (r%i == 0)
return (0);
return (1);
}

int avalaval (int r) {
int k = tet(r)-1;
while (k>=0)
if (aval(r, k--) != 1)
return (0);
return (1);
}

[Chio-nega-mikoni]

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

int tet (int);
int avalaval (int);
int aval (int, int);

int main () {
int x=1, n=5;
do if (avalaval(x)) --n;
while (n>0 && ++x);
printf ("Elapsed time=%ld\nOutput=%d", clock(), x);
return (EXIT_SUCCESS);
}

int tet (int r) {
int i=0;
while (r!=0 && ++i)
r/=10;
return (i);
}

int aval (int r, int i) {
if ((r/=(int)pow(10, i)) == 1)
return (0);
for (i=2; i <= (sqrt(r)); ++i)
if (r%i == 0)
return (0);
return (1);
}

int avalaval (int r) {
int k = tet(r)-1;
while (k>=0)
if (aval(r, k--) != 1)
return (0);
return (1);
}





الان سوال رو جواب دادید مثلا؟؟:متفکر::متفکر::متفکر:

[rahnema1]

سلام

شما برای محاسبه یک عدد اول می ایید باقیمانده تقسیم عدد، بر تمام اعداد کوچکتر از جذرش بدست میارید اما فقط کافیه باقیمانده تقسیم اون عدد بر «اعداد اول» کوچکتر از جذرش را محاسبه کنید در نتیجه لازم می شه اعداد اولی را که به دست میارید در یک مثلا آرایه ذخیره کنید که در حاسبات بعدی از اینها استفاده کنید
همچنین با تعریف عدد فوق اول متوجه می شیم که عدد فوق اول عددی است که هر زیر عدد سمت چپ آن «فوق اول» باشد بنابراین لازمه لیست اعداد فوق اول را هم در یک آرایه ذخیره داشته باشید تا در محاسبات بعدی ازش استفاده کنید که دیگه نخواهید هزار بار چک کنید که یک عدد اول هست یا نه همچنین برای جستجو در این آرایه فوق اول هم می تونید از bsearch که در stdlib قرار داره استفاده کنید. البته توی زبان ++C ساختمانهایی مثل set و unordered_set هم هست که چون برنامه شما بیشتر سبک و سیاق زبان c را داره همون bsearch سرعت را تاحد زیادی بالا می بره
یک نکته دیگه هم اینکه سعی کنید برای متغیر ها، نامهای معنی دار بذارید مثلا b یا k یا t و اینها معنا ندارند و باعث سردرگمی خواننده می شن
یک نکته دیگه اینکه اگه قراره یک تابع بیاد عدد اول محاسبه کنه باید فقط همین کار را انجام بده و اگه قراره کار دیگه ای انجام بشه توی یه تابع دیگه بذارید تا همه چی منظم و مرتب باشه

[Chio-nega-mikoni]

سلام

شما برای محاسبه یک عدد اول می ایید باقیمانده تقسیم عدد، بر تمام اعداد کوچکتر از جذرش بدست میارید اما فقط کافیه باقیمانده تقسیم اون عدد بر «اعداد اول» کوچکتر از جذرش را محاسبه کنید در نتیجه لازم می شه اعداد اولی را که به دست میارید در یک مثلا آرایه ذخیره کنید که در حاسبات بعدی از اینها استفاده کنید
همچنین با تعریف عدد فوق اول متوجه می شیم که عدد فوق اول عددی است که هر زیر عدد سمت چپ آن «فوق اول» باشد بنابراین لازمه لیست اعداد فوق اول را هم در یک آرایه ذخیره داشته باشید تا در محاسبات بعدی ازش استفاده کنید که دیگه نخواهید هزار بار چک کنید که یک عدد اول هست یا نه همچنین برای جستجو در این آرایه فوق اول هم می تونید از bsearch که در stdlib قرار داره استفاده کنید. البته توی زبان ++C ساختمانهایی مثل set و unordered_set هم هست که چون برنامه شما بیشتر سبک و سیاق زبان c را داره همون bsearch سرعت را تاحد زیادی بالا می بره
یک نکته دیگه هم اینکه سعی کنید برای متغیر ها، نامهای معنی دار بذارید مثلا b یا k یا t و اینها معنا ندارند و باعث سردرگمی خواننده می شن
یک نکته دیگه اینکه اگه قراره یک تابع بیاد عدد اول محاسبه کنه باید فقط همین کار را انجام بده و اگه قراره کار دیگه ای انجام بشه توی یه تابع دیگه بذارید تا همه چی منظم و مرتب باشه


خیلی کامل بود ممنونم..