查看完整版本 : help!!! JAVA How to get prime number in random number

me888 2013-7-24 03:32

You can ask Bill Gate whether he used it or not? 小朋友,亞叔三十幾年前識寫 sieve prime applesoft program 時, 你仲出世呢?



[url=http://www.discuss.com.hk/android][img=100,23]http://i.discuss.com.hk/d/images/r10/androidD.jpg[/img][/url]

skhui2005 2013-7-24 03:46

差不多七天,二十多個帖子,這個經典習題很難解麼?
以sieve of eratosthenes java 做 keyword Google 一下,
就找到以下答案:[url=http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes]http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes[/url]

Susan﹏汪汪 2013-7-24 12:23

[quote]原帖由 [i]skhui2005[/i] 於 2013-7-24 03:46 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=367781380&ptid=22195856][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
差不多七天,二十多個帖子,這個經典習題很難解麼?
以sieve of eratosthenes java 做 keyword Google 一下,
就找到以下答案:http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes [/quote]
啊...這個問題的確很難解決的..



[url=http://www.discuss.com.hk/iphone][img=100,23]http://i.discuss.com.hk/d/images/r10/iphoneD.jpg[/img][/url]

form5 2013-7-24 21:50

[quote]原帖由 [i]me888[/i] 於 2013-7-24 03:32 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367781209&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
You can ask Bill Gate whether he used it or not? 小朋友,亞叔三十幾年前識寫 sieve prime applesoft program 時, 你仲出世呢?

[img]http://i.discuss.com.hk/d/images/r10/androidD.jpg[/img] [/quote]
it seems to me someone is just another copycat, you certainly earn some respect from your age too, but nothing else.
[url=http://community.freepascal.org/bboards/message?message_id=307987&forum_id=24082]http://community.freepascal.org/bboards/message?message_id=307987&forum_id=24082[/url][code]program PRIMENUM(input, output);

label 1;

label 2;

var

    z : longword;

    x : longword;

    v : longword;

begin

writeln('                                           Papaphilippou Philippos 2009');

writeln('=======================================================================');

writeln('Press enter to start computing the prime numbers;  Press Pause to halt.');

write('=======================================================================');

readln;

write('2 3 ');

z := 1;

goto 2;

1:

if z mod x = 0 then begin

    goto 2;

    end;

if x <= ( z div (v))-2 then begin

    v:=x;

    x:=x+2;

    goto 1;

   end;

write(z);

write(' ');

2:

z := z + 2;

x := 3;

v := 2;

goto 1;

end.[/code]

[[i] 本帖最後由 form5 於 2013-7-24 09:57 PM 編輯 [/i]]

Susan﹏汪汪 2013-7-24 22:16

啊......汪汪想講......Sieve of Eratosthenes是最沒效率的做法:loveliness:

form5 2013-7-24 22:22

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-24 10:16 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367836748&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
啊......汪汪想講......Sieve of Eratosthenes是最沒效率的做法:loveliness: [/quote]

you are hurting someone's feelings :smile_19:

[[i] 本帖最後由 form5 於 2013-7-24 10:49 PM 編輯 [/i]]

Susan﹏汪汪 2013-7-24 23:15

.....對不起....

form5 2013-7-24 23:22

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-24 11:15 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367842413&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
.....對不起.... [/quote]
:smile_o10:  我代果位billgate 老伯原諒你啦

[color=DarkOrange]補充:三十一摟bill gate 果位[/color]

[[i] 本帖最後由 form5 於 2013-7-24 11:30 PM 編輯 [/i]]

Susan﹏汪汪 2013-7-24 23:33

[code]#include <iostream>
#include <functional>
#include <random>
using namespace std;


    const int prime[] = {
    41, 43, 47, 53, 59,
    61, 67, 71, 73, 79,
    83, 89, 97, 101, 103,
    107, 109, 113, 127, 131,
    137, 139, 149}; //total 23


unsigned GCD(unsigned a, unsigned b)
{
    return a % b ? GCD(b, a % b) : b;
}

bool test(int p)
{
    for(int i = 0; i < sizeof(prime) / sizeof(int) && sqrt(p) > prime[i]; ++i)
    {
        if(p % prime[i] == 0)
            return false;
    }
   
    return true;
}

int main()
{
    auto GetRandom = bind(uniform_int_distribution<int>(17, 3333), mt19937());
    //because 17 * 6 - 1 = 101 and 3333 * 6 + 1 = 19999
    auto add = bind(bernoulli_distribution(0.5), mt19937());
   
    int result = 0;
    while(true)
    {
        if(add())
            result = GetRandom() * 6 + 1;
        else
            result = GetRandom() * 6 - 1;
        
        if(GCD(result, 5005) != 1) continue; //5 * 7 * 11 * 13
        if(GCD(result, 7429) != 1) continue; //17 * 19 * 23
        if(GCD(result, 33263) != 1) continue; //29 * 31 * 37
        if(test(result)) break;
    }
   
    cout << result;
    return 0;
}[/code]

Susan﹏汪汪 2013-7-24 23:40

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-24 11:33 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367844007&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
#include
#include
#include
using namespace std;


    const int prime[] = {
    41, 43, 47, 53, 59,
    61, 67, 71, 73, 79,
    83, 89, 97, 101, 103,
    107, 109, 113, 127, 131,
    137 ... [/quote]用GCD來test的話似乎也不是方法....只是單單的例如5 * 7 * 11 * 13....直接的試除四次還快很多
但如果用大數來做GCD的話......又倒不如用fermat test

form5 2013-7-24 23:46

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-24 11:40 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367844682&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
用GCD來test的話似乎也不是方法....只是單單的例如5 * 7 * 11 * 13....直接的試除四次還快很多
但如果用大數來做GCD的話......又倒不如用fermat test [/quote]
冇記錯之前的話,100 至20000 好似有2273 個 prime number, 不如一串array hard code儲存,跟住random select,我估應該會快少少

[[i] 本帖最後由 form5 於 2013-7-24 11:47 PM 編輯 [/i]]

Susan﹏汪汪 2013-7-25 00:07

oops...看錯了意思...

[[i] 本帖最後由 Susan﹏汪汪 於 2013-7-25 12:12 AM 編輯 [/i]]

form5 2013-7-25 00:18

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-25 12:07 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367846954&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
你沒有見到汪汪一開始的那個list2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 14920000以內只要test呢35個數就 ... [/quote]
車,我見你樓上邊搞甘多,我都係諗住一take過 算數

Susan﹏汪汪 2013-7-25 00:35

[quote]原帖由 [i]form5[/i] 於 2013-7-25 12:18 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367847802&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

車,我見你樓上邊搞甘多,我都係諗住一take過 算數 [/quote]汪汪看錯了意思......:smile_13:
以為話generate一條prime list去做test

不如到汪汪那個帖.....講講有甚麼方法test prime num了吧

[[i] 本帖最後由 Susan﹏汪汪 於 2013-7-25 12:37 AM 編輯 [/i]]

form5 2013-7-25 00:43

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2013-7-25 12:35 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=367849149&ptid=22195856][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
汪汪看錯了意思......:smile_13:
以為話generate一條prime list去做test

不如到汪汪那個帖.....講講有甚麼方法test prime num了吧 [/quote]
我頭暈牙,我要睇返書時先記得 fft dfft ifft , 話時話,好似念咒甘,我訓先:smile_19:

skhui2005 2013-7-25 01:20

Susan﹏汪汪君:

根據你在40#的意見,儘管你認為『Sieve of Eratosthenes是最沒效率的做法』(35#),
猜想你也找不到更好的算法吧?因為 "The Fermat primality test is a probabilistic test to determine if a number is probable prime." ([url]http://en.wikipedia.org/wiki/Fermat_primality_test[/url])  ,無法求出肯定的答案。

很欣賞你有研究精神,所以多說一下我的意見:

1. Sieve of Eratosthenes 的算法簡單易懂,容易 program ,最重要是能求出肯定的答案!
2. 它的效率也不差,假設要求出 1 至 N 間的所有質數,而 N 是個天文數字的上限,
    我們未開始求解,就排除了除 2 以外的雙數,即只需檢查約 N / 2 個單數。
3. 你可以在這裏知道這算法的 Time Complexity ([url]http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes[/url])。

Susan﹏汪汪 2013-7-25 13:50

[quote]原帖由 [i]skhui2005[/i] 於 2013-7-25 01:20 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=367852211&ptid=22195856][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
Susan﹏汪汪君:

根據你在40#的意見,儘管你認為『Sieve of Eratosthenes是最沒效率的做法』(35#),
猜想你也找不到更好的算法吧?因為 "The Fermat primality test is a probabilistic test to determine if a n ... [/quote]
那跟樓主的題目寫段code吧:loveliness:



[url=http://www.discuss.com.hk/iphone][img=100,23]http://i.discuss.com.hk/d/images/r10/iphoneD.jpg[/img][/url]

鄉貢仁 2023-10-17 15:21

prime numbers 是好的編程題目.
:smile_44:

howevera 2023-10-20 17:36

[quote]原帖由 [i]鄉貢仁[/i] 於 2023-10-17 15:21 發表 [url=https://www.discuss.com.hk/redirect.php?goto=findpost&pid=562101982&ptid=22195856][img]https://www.discuss.com.hk/images/common/back.gif[/img][/url]

prime numbers 是好的編程題目.
:smile_44: [/quote]
以前考試要考
頁: 1 [2]
查看完整版本: help!!! JAVA How to get prime number in random number