the dictionary definition of prime numbers gives us a clear idea about prime number finding algorithm; ‘–noun Mathematics.
a positive integer that is not divisible without remainder by any integer except itself and 1, with 1 often excluded: The integers 2, 3, 5, and 7 are prime numbers. ‘ according to http://dictionary.reference.com/browse/prime+number.
hence the most primitive algorithm is dividing the number by all the positive numbers between 2 and the number-1 and waiting for non-zero reminders from all.
however it is not really the most practical way.
first of all it is obvious that any numbers except for 2 cannot be divided without reminder by its decrement. this way of thinking leads us to question the range of the numbers to be used as divider. logically the limit should be between 2 and square root of the number. the explanation is simple; lets assume that the number is not prime and we divide it with a number bigger than its square root, in that case the result will be a number between 2 and the number’s square root, which we should have already tested (since we start the division test in order starting from two).
secondly the test should be done only with prime numbers, not all. the reason is quite simple, if X divides Y then all the multipliers of X also divides Y. think about dividing 600 by 30; 600 can also be divided by 2, 3 and 5 which are the multipliers of 30.
lastly there is no point of testing even numbers as they already can be divided by 2. by doing that, for finding prime number in a range, we also prevent the division by 2 tests.
here is the python code for finding prime numbers in the range of 2 to 1′000′000, takes aroun 5.4 seconds on my laptop.
-
from math import sqrt
-
import time
-
t1 = time.time()
-
primenumbers=[2,3,5]
-
-
for i in range(7,1000000,2):
-
sq = sqrt(i)+1
-
for j in primenumbers:
-
if sq < j:
-
primenumbers.append(i)
-
#print i, len(primenumbers)
-
break
-
-
if i % j == 0:
-
break
-
-
print len(primenumbers)
-
t2 = time.time()
-
print (t2 – t1)
svn checkout http://balyoz.googlecode.com/svn/trunk/ balyoz-read-only
http://code.google.com/p/balyoz/
Balyoz is a 3D shooter game having been written using OGRE engine.The aim is to provide a interesting
and enjoyable game play experience for the player and still in development.In order to achieve this purpose,
we have been using PyhsicX physic engine to provide a more realistic and unique game experience.Although
Balyoz is a classic 3D shooting game,it has also some different features then classic shooting games
offer and full of challenge even its underlying structure.The war plane will be flying over a terrain and be
capable of moving both X and Z direction.Besides, there will be different weapon options which makes
the game play more enjoyable.In Balyoz, other then enemy air units, there will be navy and ground units
which will be shooting to out plane as well.To destroy ground units, player have to use bombs with
the correct timing and position combination.I would like to give some information about the underlying
structure of the Balyoz game.
1.XML Based Definition
In order to achieve flexibility, unit definitions, weapons, levels, maps etc.. are defined XML files.
They are loaded either on game initialization stage or level lodging stage.It provides us a great
flexibility to alter the attributes, for example weapon attributes like speed, range or controller
type, or level attributes like the unit types in level and their positions, without changing even
one line code.It also prevents us to recompile the code for each time we change a attribute.
Let us have a look a example xml used in game.
<?xml version="1.0" ?>
<weapons>
<weapon>
<name>bazooka</name>
<mesh>cube.mesh</mesh>
<reloadtime>500</reloadtime>
<numofbullets>
<capacity>1000</capacity>
<initial>1</initial>
<maximum>9</maximum>
<minimum>1</minimum>
<anglebetweenbullets>18</anglebetweenbullets>
</numofbullets>
<bullet>
<initialspeed>10</initialspeed>
<maximumspeed>-100</maximumspeed>
<power>100</power>
<radius>10</radius>
<effect>linear</effect>
<lifetime>4.5</lifetime>
<particles>Examples/Smoke</particles>
<explosion>explosion</explosion>
<controller>dummy</controller>
</bullet>
</weapon>
</weapons> |
XML structure in terms of game is shown below,
Game.xml
|
Levels.xml ____
| |
Map.xml Terrain.xml
|
Units.xml
|
Weapons.xml
|
BulletController.xml
So,if it is needed to load a unit into the game, first units.xml file will be read and unit attribute
will be figured out from units.xml file.Then, weapon names related to that unit will be read from
units.xml file and with that reference, weapon attributes will be taken from weapon.xml file.
After that, the information about by which weapon controller it will be controlled will be read
from BulletController.xml file since for example guided missiles should be controlled in a
different way.As you can see, even controller types are defined in xml files and for sure, this
system provides a great flexibility when we want to add a new weapon to a unit, or a new
unit to a level.It is one of the most powerful feature of Balyoz in terms of design.
2.Controller Design
As a design decision, a main controller is implemented which is responsible to process
and update all the game events. Main game controller process the events via a event
queue it contains. Besides, there are some sub-controllers like Unit Controller or
Collision Controller which are responsible for creating related game events and adding
the main controller`s queue.So, before each frame is rendered, first all the controllers
are executed, produced related event and added to main controller`s event queue. Then
before rendering the frame (or after) this queue is processed by main controller and game
word is updated. Separating controlling behaviors to different controllers is also provides a
flexibility to implement control behavior and maintaining the code.Moreover, game core
talks to just main controller and does not need to know about sub-controllers.These design
decisions are shown by images below,
Balyoz is still in its early stage of development.I will be adding news about the progress of game.Beside, screenshots and videos will be added soon as well.
