Prime number generator
105 views
Skip to first unread message
MihaR
Jul 8, 2011, 9:12:09 PM7/8/11
to Tile Factory
I have managed to create a prime number generator. My version creates
all prime numbers, which are smaller than 67. It can be expanded to
any number you want (only limitation is space, needed for logical
units).
The output is located in lower left corner, white = non prime and
black = prime.
It is quite slow. If n is a prime, it needs more than (n+1)*n/2
seconds to confirm that. If n is even number, it takes more than 2n
seconds to confirm that is not prime. There is also reset time after n
was checked, which takes n seconds. Basically, my estimation is that
it takes few hours to check numbers 1-67 on fast speed. I will test it
overnight. Below are some intermediate times:
4 minutes to reach number 12
13 minutes to reach number 22
23 minutes to reach number 29
There are three components:
-upper conveyor with one tile, which serves as a dividend or input. If
tile is on sensor 35, than number 35 is being checked.
- lower conveyer with one tile, which serves as a divisor (lets say
that tile is on sensor 5 for this explanation)
- connected mems, which serve as a some kind of quotient. At the
beginning of the cycle, first mem is turned on. When the fifth mem is
on, it again turns on the first mem and so on (every fifth mem is on).
The situation is like:
X upper conveyor
X
lower conveyor
0000X0000X0000X0000X0000X0000X0000X mems
The number is not prime if two sensor and two mems are on at the same
time:
- sensor 35 in upper conveyor
- sensor 5 in lower conveyor
- mems 5 and 35
If you have any question, I will be glad to answer, because I am
really proud that I managed to build this generator.
eNol1+uW4rgVgFGQhWSEMQYD5n4vyBPk/V8rvzLba+as3YiuKT
r5mtJhppPJf97T/6UYQvpOp/kXQv7OQvrFKscY5imkeaZmTmFB
w5KWFWs6ejak6PuomVNY0LCkpWPFhjU9W3bjo9fYsWfgwJETF8
5cuXHnwZMXbz788R1VeM0/3nx48eTBnRtXLpw5ceTAwD6m6rsN
1Xcfqt8uVH8eP7x58uLBnSsXzhwY2LNjS89m5PV6tuzZMXDgyI
kzF67cuPPgyYs3H/7Gr3vNIyfWnnesWNLSsKBQkxG6Sv79mozg
VWFBw5IV3fiatPsw+9uF2YcXTx7cuXLmxIEdPRu27Bk4cuHGm0
SmprBgScuKjjUN3hSzr/6TKlXTkGbTKi1n3rvRG/Sbp+lXqvSr
q/RdTFIsYTmrvYdr70Vq5hQWNCxpWdGxZkPPlh17Bg4cOXHmwp
Ubdx48efHmwx/f0ZziOR/evHjy4M6NKxfOnDhyYM/Aji09GxKZ
mjmFBQ1LWlZ0rEuqJlm3FGbTnCYhJ+XSpMpJRl9b6DoPs0kJk1
B8bZGm04V/b+7rTZpMG783ProVpiVNcp8mNXMWFBqWtHSs2LCm
Z8uOPQMHjpw4c+HKnRsPnrx48+GPL7+tx8FzPrx58uLBnRtXLp
w5ceTAwJ4dW3o2rOlY0bKkYUFhTk0mDamZXkITjtPl5BKO4RBK
OM9SuIRJ0jaTtM7UI8/nI+cycl6MnJuR83Lk3I6cVyPnbuS8Hj
lvRs79yHk7ct6NnPcj52HkfBg5H0fOp5HzeeR8GTlfR863kfPd
493jY+T8HDm/Rs7vkfNn5Pw3cv7yG3l/zby/0jZMK39vqdWDmt
Q5UzOnsKBhScuKjg1renZsx+/xGoUFDUtaVnSs2dCzY892fPS9
AweOnMZHv39g4Oz5hSs37jx48uLDmz++/FbOvu/LhzcvHjy5c+
PKZXx9Tq2fK99XrVPVTEI1671n+lTFVZjOdqma+70y8fN6DNX0
4GfzGCbTU8qtBVidp/PGX9bsPE2JTM2cwoKGeJ5WC69T1e7viS
vTuASmyfg15JBj/XV5mvwdL865mzVVvlb9e53mb54sJnOz+Jaw
MGUyny4mi6nxZi+xeHS5VY3vbaomzD0bv9pMm1/9nfvhcJrOvd
fr6Xw85W1t5qaYhWnM0rRmZTqzNhvTm/GfndmbwRzM0ZzM2VzM
1dzM3TzM07zM23zMn/ma3+63++6/+z/zMW/zMk/zMHdzM1dzMW
dzMkdzMIMZ/9mZ8X9QbzZmbTqzMq1ZmsYsTDFzU5ts0j5vc69C
r0KvQK9Ar0CvQK9Ar0CvQK9Ar8CYoFegH/9ABXoFegV6BXoFeg
V6BXoFegV6BXoFegV6BXoFegV6BXoFtgoMCgwKDAoMCgwKDAoM
CgwKDAoMCgwKDAoMCgwKDAqMCQYFhvEvRIFBgUGBQYFBgUGBQY
FBgUGBQYFBgUGBQYEh7dOQaw1qDWr7rC79otah1qHWodah1qHW
odah1qHWodah1qH2h9Y61DrUOtQ61DrUOtQ61DrUOtQ61DrUOt
Q61DrUOtTf/jvXoehQdCg6FB2KDkWHokPRoehQdCg6FB2KDkWH
okPRoehQdCg6FB2KDkWHokPRoehQdCg6FB2KDkWHokPRoVghto
IWqR4/odR2um2uRdIiaZG0SFokLZIWSYukRdIiaZG0SFokLZIW
SYukRdIiaZG0SFokLZIWSYukRdIiaZG08HP/S9/yy1pkLbIWWY
usRdYia5G1yFpkLbIWWYusRdYia5G1yFpkLbIWWYusRdYia5G1
yFpkLbIWWYusRdYia5G18JFEC59M6qCFTx4umOTSSS6RtAxaBC
2CFkGLoEXQImgRtAhaBC2CFkGLoEXQImgRtAhaBC2CFkGLoEXQ
ImgRtAhaBC0qLaIWUYuoRdQiahGf+R51iDpEHeIlP+Ijn6MWUY
uoRdQiahG1iFpELaIWUYuoRdQiahG1iFpELaIWUYuoRdQiahG1
SDO/zLw9Zj7pkZ3JJIrfW9CwpGVFx5oNPVt27Bk4cOTEmQtXbt
x58OTFmw9/fPmN/Nl/fHjz4smDOzeuXDhz4siBgT07tvRsWNOx
omVJw2L8/8nMjmduj9hiPldtbZG+6ucUFjQsaVnRsWZDz5Ydew
YOHDlx5sKVG3cePHnx5sMfX35bj4PnfHjz4smDOzeuXDhz4siB
gT07tvRsWNOxomVJw4LCnJpMGm3l2ubWLmntktZGbe2T1j5p7Z
PWPmntk9Y+ae2T1j5phWjtk9Y+ae2T1j5p7ZPWPmntk9Y+ae2T
1j5p7ZPWPmntk9Y+ae2T1j5p7ZPWPmntk9Y+WdknnX3S2Sedfd
LZJ5190tknnX3S2SedfdLZJ5190tknnX3S2SedfdLZJ5190tkn
nb+gzj7p7JPOPunsk84+6eyTzj7p7JPOPunsk84+6eyTzpu7c3
e07o7W3dG6O1p3R+vuaN0drbujdXe07o7W3dG6O1p3R+vu8N/G
WgQtghZBi6BF0CJoEbQIWgQtghZBi6BF0CJoEbQIWgQtwrd1d6
y+UYuoRdQiahG1iFpELaIWUYuoRdQiahG1iFpELaIWUYuoRdQi
9p17o3N/dO6Ozt3RuTs6d0fn7ujcHZ27o3N3dO6Ozt3RuTu61F
YumWpVM6ewoGFJy4qONRt6tuzYM3DgyIkzF67cuPPgyYs3H/74
8lt57Dznw5sXTx7cuXHlwpkTRw4M7NmxpWfDmo4VLUsaFhTm1G
QSZl31rKeXWR/rZpK2zSTWfnZ6l2tfrWKNSVsfvHezXaZmTmFB
w5KWFR1rNvRs2bFn4MCRE2cuXLlx58GTF28+/PHdVavZbvzJ9o
l9wdxH58ksTY+T43ScAye/nqanMJ4ubsddtZ7tPL9U63BpLtW5
ucxIZGrmFBY0xHOZRB/mfZSfNIzn6cX90Wf3W8hVXSkUstcN0X
83fKfT8IuTNPnv//8BoWcZDQ==
all prime numbers, which are smaller than 67. It can be expanded to
any number you want (only limitation is space, needed for logical
units).
The output is located in lower left corner, white = non prime and
black = prime.
It is quite slow. If n is a prime, it needs more than (n+1)*n/2
seconds to confirm that. If n is even number, it takes more than 2n
seconds to confirm that is not prime. There is also reset time after n
was checked, which takes n seconds. Basically, my estimation is that
it takes few hours to check numbers 1-67 on fast speed. I will test it
overnight. Below are some intermediate times:
4 minutes to reach number 12
13 minutes to reach number 22
23 minutes to reach number 29
There are three components:
-upper conveyor with one tile, which serves as a dividend or input. If
tile is on sensor 35, than number 35 is being checked.
- lower conveyer with one tile, which serves as a divisor (lets say
that tile is on sensor 5 for this explanation)
- connected mems, which serve as a some kind of quotient. At the
beginning of the cycle, first mem is turned on. When the fifth mem is
on, it again turns on the first mem and so on (every fifth mem is on).
The situation is like:
X upper conveyor
X
lower conveyor
0000X0000X0000X0000X0000X0000X0000X mems
The number is not prime if two sensor and two mems are on at the same
time:
- sensor 35 in upper conveyor
- sensor 5 in lower conveyor
- mems 5 and 35
If you have any question, I will be glad to answer, because I am
really proud that I managed to build this generator.
eNol1+uW4rgVgFGQhWSEMQYD5n4vyBPk/V8rvzLba+as3YiuKT
r5mtJhppPJf97T/6UYQvpOp/kXQv7OQvrFKscY5imkeaZmTmFB
w5KWFWs6ejak6PuomVNY0LCkpWPFhjU9W3bjo9fYsWfgwJETF8
5cuXHnwZMXbz788R1VeM0/3nx48eTBnRtXLpw5ceTAwD6m6rsN
1Xcfqt8uVH8eP7x58uLBnSsXzhwY2LNjS89m5PV6tuzZMXDgyI
kzF67cuPPgyYs3H/7Gr3vNIyfWnnesWNLSsKBQkxG6Sv79mozg
VWFBw5IV3fiatPsw+9uF2YcXTx7cuXLmxIEdPRu27Bk4cuHGm0
SmprBgScuKjjUN3hSzr/6TKlXTkGbTKi1n3rvRG/Sbp+lXqvSr
q/RdTFIsYTmrvYdr70Vq5hQWNCxpWdGxZkPPlh17Bg4cOXHmwp
Ubdx48efHmwx/f0ZziOR/evHjy4M6NKxfOnDhyYM/Aji09GxKZ
mjmFBQ1LWlZ0rEuqJlm3FGbTnCYhJ+XSpMpJRl9b6DoPs0kJk1
B8bZGm04V/b+7rTZpMG783ProVpiVNcp8mNXMWFBqWtHSs2LCm
Z8uOPQMHjpw4c+HKnRsPnrx48+GPL7+tx8FzPrx58uLBnRtXLp
w5ceTAwJ4dW3o2rOlY0bKkYUFhTk0mDamZXkITjtPl5BKO4RBK
OM9SuIRJ0jaTtM7UI8/nI+cycl6MnJuR83Lk3I6cVyPnbuS8Hj
lvRs79yHk7ct6NnPcj52HkfBg5H0fOp5HzeeR8GTlfR863kfPd
493jY+T8HDm/Rs7vkfNn5Pw3cv7yG3l/zby/0jZMK39vqdWDmt
Q5UzOnsKBhScuKjg1renZsx+/xGoUFDUtaVnSs2dCzY892fPS9
AweOnMZHv39g4Oz5hSs37jx48uLDmz++/FbOvu/LhzcvHjy5c+
PKZXx9Tq2fK99XrVPVTEI1671n+lTFVZjOdqma+70y8fN6DNX0
4GfzGCbTU8qtBVidp/PGX9bsPE2JTM2cwoKGeJ5WC69T1e7viS
vTuASmyfg15JBj/XV5mvwdL865mzVVvlb9e53mb54sJnOz+Jaw
MGUyny4mi6nxZi+xeHS5VY3vbaomzD0bv9pMm1/9nfvhcJrOvd
fr6Xw85W1t5qaYhWnM0rRmZTqzNhvTm/GfndmbwRzM0ZzM2VzM
1dzM3TzM07zM23zMn/ma3+63++6/+z/zMW/zMk/zMHdzM1dzMW
dzMkdzMIMZ/9mZ8X9QbzZmbTqzMq1ZmsYsTDFzU5ts0j5vc69C
r0KvQK9Ar0CvQK9Ar0CvQK9Ar8CYoFegH/9ABXoFegV6BXoFeg
V6BXoFegV6BXoFegV6BXoFegV6BXoFtgoMCgwKDAoMCgwKDAoM
CgwKDAoMCgwKDAoMCgwKDAqMCQYFhvEvRIFBgUGBQYFBgUGBQY
FBgUGBQYFBgUGBQYEh7dOQaw1qDWr7rC79otah1qHWodah1qHW
odah1qHWodah1qH2h9Y61DrUOtQ61DrUOtQ61DrUOtQ61DrUOt
Q61DrUOtTf/jvXoehQdCg6FB2KDkWHokPRoehQdCg6FB2KDkWH
okPRoehQdCg6FB2KDkWHokPRoehQdCg6FB2KDkWHokPRoVghto
IWqR4/odR2um2uRdIiaZG0SFokLZIWSYukRdIiaZG0SFokLZIW
SYukRdIiaZG0SFokLZIWSYukRdIiaZG08HP/S9/yy1pkLbIWWY
usRdYia5G1yFpkLbIWWYusRdYia5G1yFpkLbIWWYusRdYia5G1
yFpkLbIWWYusRdYia5G18JFEC59M6qCFTx4umOTSSS6RtAxaBC
2CFkGLoEXQImgRtAhaBC2CFkGLoEXQImgRtAhaBC2CFkGLoEXQ
ImgRtAhaBC0qLaIWUYuoRdQiahGf+R51iDpEHeIlP+Ijn6MWUY
uoRdQiahG1iFpELaIWUYuoRdQiahG1iFpELaIWUYuoRdQiahG1
SDO/zLw9Zj7pkZ3JJIrfW9CwpGVFx5oNPVt27Bk4cOTEmQtXbt
x58OTFmw9/fPmN/Nl/fHjz4smDOzeuXDhz4siBgT07tvRsWNOx
omVJw2L8/8nMjmduj9hiPldtbZG+6ucUFjQsaVnRsWZDz5Ydew
YOHDlx5sKVG3cePHnx5sMfX35bj4PnfHjz4smDOzeuXDhz4siB
gT07tvRsWNOxomVJw4LCnJpMGm3l2ubWLmntktZGbe2T1j5p7Z
PWPmntk9Y+ae2T1j5phWjtk9Y+ae2T1j5p7ZPWPmntk9Y+ae2T
1j5p7ZPWPmntk9Y+ae2T1j5p7ZPWPmntk9Y+WdknnX3S2Sedfd
LZJ5190tknnX3S2SedfdLZJ5190tknnX3S2SedfdLZJ5190tkn
nb+gzj7p7JPOPunsk84+6eyTzj7p7JPOPunsk84+6eyTzpu7c3
e07o7W3dG6O1p3R+vuaN0drbujdXe07o7W3dG6O1p3R+vu8N/G
WgQtghZBi6BF0CJoEbQIWgQtghZBi6BF0CJoEbQIWgQtwrd1d6
y+UYuoRdQiahG1iFpELaIWUYuoRdQiahG1iFpELaIWUYuoRdQi
9p17o3N/dO6Ozt3RuTs6d0fn7ujcHZ27o3N3dO6Ozt3RuTu61F
YumWpVM6ewoGFJy4qONRt6tuzYM3DgyIkzF67cuPPgyYs3H/74
8lt57Dznw5sXTx7cuXHlwpkTRw4M7NmxpWfDmo4VLUsaFhTm1G
QSZl31rKeXWR/rZpK2zSTWfnZ6l2tfrWKNSVsfvHezXaZmTmFB
w5KWFR1rNvRs2bFn4MCRE2cuXLlx58GTF28+/PHdVavZbvzJ9o
l9wdxH58ksTY+T43ScAye/nqanMJ4ubsddtZ7tPL9U63BpLtW5
ucxIZGrmFBY0xHOZRB/mfZSfNIzn6cX90Wf3W8hVXSkUstcN0X
83fKfT8IuTNPnv//8BoWcZDQ==
CJ
Jul 8, 2011, 9:22:39 PM7/8/11
to tile-f...@googlegroups.com
anyway you think you could make improvements?
MihaR
Jul 9, 2011, 5:39:05 AM7/9/11
to Tile Factory
No significant improvement in this stage, becouse I wanted to build
the prime number generator, which does not require any mathematical
knowledge (no shortcuts). I could probably change some small things,
but that would results in a improvements in the range of n second per
cycle (cycle is now (n+1)*n/2 seconds). This are small improvements,
the generator would take 29 minutes instead 30 to reach number 33.
Some shorcuts, which are not used and could be:
Example 1: If number is not divided with 2, than it also will not be
divided by any multiply of 2 (4, 6, 8 ...). The generator is "stupid"
and still checks if number can be divided by 4, 6, 8....
Example 2: We all know that is enough to test numbers smaller than
sqrt (n) to see, if the number n is prime. I do not know and until now
I did not try how to produce sqrt (n). I could limit the checking to n/
3, or something like that, but this is again shortcut, obtained from
mathematical knowledge.
However, while answering you question, I got an idea for mathematical
knowledge based prime number generator...
the prime number generator, which does not require any mathematical
knowledge (no shortcuts). I could probably change some small things,
but that would results in a improvements in the range of n second per
cycle (cycle is now (n+1)*n/2 seconds). This are small improvements,
the generator would take 29 minutes instead 30 to reach number 33.
Some shorcuts, which are not used and could be:
Example 1: If number is not divided with 2, than it also will not be
divided by any multiply of 2 (4, 6, 8 ...). The generator is "stupid"
and still checks if number can be divided by 4, 6, 8....
Example 2: We all know that is enough to test numbers smaller than
sqrt (n) to see, if the number n is prime. I do not know and until now
I did not try how to produce sqrt (n). I could limit the checking to n/
3, or something like that, but this is again shortcut, obtained from
mathematical knowledge.
However, while answering you question, I got an idea for mathematical
knowledge based prime number generator...
CJ
Jul 9, 2011, 6:32:12 AM7/9/11
to tile-f...@googlegroups.com
Cool! But I still don't think the sieve of Eratosthenes can be programmed.
CJ
Jul 9, 2011, 6:42:31 AM7/9/11
to tile-f...@googlegroups.com
wait. any number less than 100 and is not divisible by 2 3 5 or 7 is prime?
Iván Nieto
Jul 9, 2011, 3:50:02 PM7/9/11
to Tile Factory
On Jul 9, 6:42 am, CJ <cjquinesp...@gmail.com> wrote:
> wait. any number less than 100 and is not divisible by 2 3 5 or 7 is prime?
Correct. To determine if N is prime, you only need to show that N is
> wait. any number less than 100 and is not divisible by 2 3 5 or 7 is prime?
not divisible by any prime up to the square root of N.
CJ
Jul 9, 2011, 8:42:35 PM7/9/11
to tile-f...@googlegroups.com
This lightbulb suddenly lit over my head.
MihaR
Jul 10, 2011, 5:09:21 AM7/10/11
to Tile Factory
That is my next step to add additional loop, which will select only
prime numbers. I have an idea how to that, but I am still thinking how
to produce square root of N.
I do not want to directly check only numbers 2 3 5 and 7, because this
is "cheating" in my opinion. My plane is to first produce prime 2 3 5
7 and then use them for checking.
prime numbers. I have an idea how to that, but I am still thinking how
to produce square root of N.
I do not want to directly check only numbers 2 3 5 and 7, because this
is "cheating" in my opinion. My plane is to first produce prime 2 3 5
7 and then use them for checking.
Reply all
Reply to author
Forward
0 new messages