تشخیص تعداد اعداد اول بین 1 تا عدد وارد شده

[kingdaniyal]

سلام دوستان
من میخوام تو برنامم یه عددو وارد کنم و خود برنامه تشخیص بدهد که چند عدد اول بین 21 تا عدد وارد شده وجود دارد
من برنامه زیرو نوشتم(میدونم برناممو بد نوشتم) اما کار نمیده و فقط تشخیص میدهد که عدد وارد شده اول است یا نه
کار این برنامه این است که عدد را دریافت میکند و سپس تشخیص میدهد اول است یا نه اگر اول بود ادامه برنامه اجرا بشود اما اگر عدد وارد شده اول نبود عدد -1 نمایش داده شود و سپس از برنامه خارج میشود.

import java.util.Scanner;

public class One{

    public static void main(String[] args){

    Scanner input=new Scanner(System.in);

    int n,count=1,not=-1;

    boolean flag=true;

    System.out.print("Please Enter Integer Number : ");

    n=input.nextInt();

    if (n<=1){

        System.out.println(not);

        }

    else if (n==2){

        System.out.println(count);

        }

    else if (n%2==0){

        System.out.println(not);

        }

    else

        for (int i=3; flag==true && i*i<=n; i+=2){

            if((n%i)==0){

                flag=false;

                System.out.println(not);

                }

            }

        if (flag==true){

            for (int j=3,i=n; j<=i && 2<i; j+=2,i-=2){

                if ((i%j)!=0){

                    count=count+2;

                    }

                }

            System.out.println(count);

        }    

    }

}

ممنون میشوم اگر کمکم کنید
با ساس فراوان

[محمد فدوی]

باور کن برنامتو نفهمیدم!
اگه میخوای صرفاً یه برنامه بنویسی که تشخیص بده یه عدد اوله یا نه، دو حالت وجود داره:
۱. میخوای یه عدد کوچیک (در محدوده‌ی اعداد int یا long) رو تشخیص بدی ولی با ضریب اطمینان بالا: از این تابع ساده استفاده کن:

    public static boolean isPrime(int n) {

        if (n <= 1) {

            return false;

        }

        if (n % 2 == 0) {

            return false;

        }





        for (int i = 3; i * i <= n; i += 2) {

            if (n % i == 0) {

                return false;

            }

        }





        return true;

    }

اینم چندوقت پیش یکی بم نشون داد که خیلی جالب و ساده بود اما نمیدونم کدومشون رفتار بهتری در مقابل اعداد مختلف دارن:

    public static long factorial(int n) {

        return n > 1 ? n * factorial(n - 1) : 1;

    }

    

    public static boolean isPrime(int n) {

        if(n <= 1) return false;

        return factorial(n - 1) % n == n - 1;

    }

ولی این دومی مسلما فقط تا موقعی کار میکنه که فاکتوریل عدد قابل محاسبه باشه که یه ضعف بزرگه.

۲. میخوای یه عدد خیلی بزرگ (یه عدد BigInteger) رو تست کنی: باید بدونی اینکار با ضریب اطمینان ۱۰۰٪ ممکن نیست (در عمل) ولی میشه بصورت احتمالی بررسی کرد این مورد رو:

        BigInteger bigint = new BigInteger("12345678987654321234567898765432123456  789");

        System.out.println(bigint.isProbablePrime(80));

به جای اون 80 باید ضریب اطمینانت قرار بگیره.

اما اگه میخوای اعداد اول بین یک تا n رو داشته باشی (یا حالا تعدادشونو داشته باشی) من خودم زیاد با این مسئله درگیر بودم. به یه الگوریتم رسیدم که الان دارمش اگه اشتباه نکنم. اگه میخوای پیداش کنم برات.

[kingdaniyal]

ممنون از اینکه پاسخ گو بودید
دقیقا من میخوام تعداد اعداد اول بین 1 تا n رو پیدا کنم
من خودم خیلی روش کار کردم اما هر کاری کردم جواب نداد

[محمد فدوی]

من اینو با #C نوشته بودم و برپایه‌ی غربال اراتستن. البته به نظرم خیلی میشه از این بیشتر بهینه سازیش کرد... مثلا اگه برای یه تعداد معلوم ولی زیاد نیاز داریش اگه به جای ArrayList از یه آرایه استفاده کنی مطمئنا خیلی تو سرعتش تاثیر داره. یا مثلا برای تعداد خیلی زیاد شاید بشه گام‌های حلقه رو برای اعداد اول بزرگتر از ۱۰۰ تغییر داد تا سرعت زیاد شه ولی اعداد اول دو قلو رو پیدا نکنه و از این کارا!

    public static ArrayList<Integer> getPrimes(int n) {

        ArrayList<Integer> primes = new ArrayList<>();

        

        if(n <= 1) { 

            return primes;

        }

        

        primes.add(2);

        main_loop: for(int i = 3; i <= n; i += 2) {

            for(Integer prime : primes) {

                if(i % prime == 0) {

                    continue main_loop;

                }

            }   

            primes.add(i);

        }

        return primes;

    }

روی سیستم من تا ۱۰۰۰۰۰۰ خوب جواب داد نسبتا. ولی اگه وابسته به نیازت یه چیزاییش رو تغییر بدی و مخصوصا اگه با ++C پیاده سازیش کنی بهتر نتیجه میگیری.

    public static void main(String[] args) {

        ArrayList<Integer> primes = getPrimes(1000000);

        try(FileOutputStream fos = new FileOutputStream("primes.list");

            PrintWriter pw = new PrintWriter(fos)) {

            for(Integer prime : primes) {

                pw.println(prime);

            }

        } catch (IOException ex) {

            ex.printStackTrace();

        }

    }

امیدوارم بت کمک کنه.

[kingdaniyal]

ممنون اون جرقهه زده شد مممممنون